2020牛客暑期多校训练营（第六场）B-Binary Vector

题目大意

设A={0,1}，每天Roundgod从（即维度为n，每一位由01组成的所有向量的集合）中随机选择一个二进制向量。现在他想知道n天中选取n个线性独立向量的概率。
设表示n的答案，最后输出 ， 表示异或。

线性独立是什么？（其实就是任意一个向量不能通过其他两个的“加减”运算得到）
https://baike.baidu.com/item/%E7%BA%BF%E6%80%A7%E7%8B%AC%E7%AB%8B

解题思路

由于这n个向量线性独立，所以张成了(N维)满秩空间，每一个向量都不属于之前的空间，总共有个向量。

我们先设有这些向量。
当n=1时，有与这2个向量与线性相关；
当n=2时，有这4个向量与线性相关；
当n=3时，有这8个向量与线性相关；

所以，对于每个i，会有个向量线性相关，所以有个向量线性独立（无关）。
那么就很好做了，先得出一个easy的结论：。接着推导：

（最后一步是将n-i换为i）

AC代码

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long a[20000010],x=5e8+4,y=5e8+4;
int main()
{
    int n,t,i;
    a[1]=5e8+4;
    for(i=2;i<=2e7;i++)
    {
        x=x*y%mod;
        a[i]=(a[i-1]-a[i-1]*x)%mod+mod;
    }
    for(i=2;i<=2e7;i++) a[i]^=a[i-1];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        printf("%lld\n",a[n]);
    }
    return 0;
}