B-Binary Vector

链接：https://ac.nowcoder.com/acm/contest/5671/B
来源：牛客网

题意：

给你一个n，让你求出n个n维向量线性无关的概率，向量由0或1组成

solution：

找规律，找出f1 * 3/4=f2,f2 * 7/8=f3，所以 f_(n-1) * (2^n-1)/(2^n)=f_n
由费马小定理可知 ,所以只要求出2的-1次的逆元，可以推广到2^-n的逆元

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
#define INF 0x3f3f3f3f

const int mod=1e9+7;
ll f[20000008];
int t,x;
ll b,c=2;
int main()
{

    f[1]=500000004;
    b=500000004;
    for(int i=2;i<=20000000;i++)
    {
        c=c*2%mod;
        b=b*f[1]%mod;
        f[i]=(c-1)*f[i-1]%mod*b%mod;
    }
    for(int i=2;i<=20000000;i++)
        f[i]=f[i-1]^f[i];
    cin>>t;
    while(t--)
    {
       cin>>x;
       cout<<f[x]<<endl;
    }
    return 0;
}