B. Binary Vector

传送门

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

题解：

 O(n) 维护2的幂和2的幂的逆元。 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int N = 2e7 + 5;
 
ll f[N], c[2 * N];
 
void init() {
    f[1] = 500000004;
    ll a = 2, b = f[1];
    for(int i = 2; i < N; ++i) {
        a = a * 2 % mod;
        b = b * f[1] % mod;
        f[i] = f[i - 1] * (a - 1) % mod;
        f[i] = f[i] * b % mod;
    }
    for(int i = 2; i < N; ++i)
        f[i] ^= f[i - 1];
}
 
int main()
{
    init();
    int t, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        cout<<f[n]<<'\n';
    }
    return 0;
}