Binary Vector

题意：
随机n个n维01向量，询问这个n个向量线性无关的概率？

思路：
观察样例，我们发现f(i)初始为1，分子开始乘1，分母乘2，然后每次乘前一次乘的2倍+1，分母每次乘前一次的二倍。
由于n<=2*10^7,所以我们打表。
我们先打出f(i)的表，f(1)=1/2的逆元ans[1]=500000004;
f(2)=1/2 * (1 * 2 +1)/(2 * 4)=1/2 * (1 * 2 +1) * (1/(2 * 4));
1/2的逆元为ans[1]，1/4的逆元为ans[1] * ans[1]，1/8的逆元为ans[1] * ans[1] * ans[1]；
这样理解你就可以线性求出f(i)的逆元后的表。

代码：

#include <bits/stdc++.h>
#define ll long long
#define db double
#define iosks std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e7+10;
const ll mod=1e9+7;

ll pow2(ll a,ll b) {ll s=1; while(b) {if(b&1) s=(s*a)%mod; a=(a*a)%mod; b/=2; } return s;}

int T;
ll n,ans[N];

int main()
{
    iosks;
    ans[1]=500000004;
    ll pa=500000004, pan=1;
    for(int i=2;i<=N;i++)
    {
        pa=pa*ans[1]%mod;
        pan=(pan*2+1)%mod;
        ans[i]=(ans[i-1]*pan)%mod*pa%mod;
    }
    for(int i=2;i<N;i++) ans[i]=(ans[i]^ans[i-1]);
    cin>>T;
    while(T--){
        cin>>n;
        cout<<ans[n]<<endl;
    }
    return 0;
}