B-Binary Vector

题目链接：https://ac.nowcoder.com/acm/contest/5671/B
题目大意:
随机生成n个n维{0,1}组成的向量，它们线性无关的概率记为f(n)
求解f(1)⊕f(2)⊕....⊕f(N)
解题思路：
由于这N个向量线性无关，则这N个N维向量组的秩为N，考虑每次将随机生成的向量加入之前向量组中，那么最后N个向量线性无关当且仅当每次加入的向量都不属于之前的空间。
那么每次可以将随机生成的向量加入之前的向量组中的概率是(2^N-2^i)/2^N, 分子可以这样理解：2^N是所有的情况，2^i是所有在之前的向量组(空间)的情况。
从而推出f(N)的公式。

但N是2e7啊，会超时。
虽然之前这种情况我们总会考虑找规律，但下次不妨也尝试一些递推：）
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e7+7;
const int mod = 1e9+7;
ll a[maxn];

ll q_pow(ll a, ll b, ll m){
    ll ans = 1;
    while(b > 0){
        if(b & 1){
            ans = ans * a % m;
        }
        a = a * a % m;
        b >>= 1; 
    } 
    return ans;
}

int main()
{
    ll x = q_pow(2,mod-2, mod);
    ll p = x, q = 2;
    a[1] = x;
    for(ll i = 2; i <= maxn; i++) {
        p *= x; p %= mod;
        q *= 2; q %= mod;
        a[i] = a[i-1]*p%mod*(q-1+mod)%mod;
    }
    for(int i = 2; i <= maxn; i++) a[i] ^= a[i-1];

    int T;
    scanf("%d",&T);
    while(T--)
    {
        ll n;
        scanf("%lld",&n);
        printf("%lld\n",a[n]);
    }

}