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

题目大意

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

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

解题思路

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

我们先设有 $\vec a,\vec b,\vec c...$ 这些向量。
当n=1时，有与 $\vec 0,\vec a$ 这2个向量与 $\vec a$ 线性相关；
当n=2时，有 $\vec 0,\vec a,\vec b,\vec a+\vec b$ 这4个向量与 $\vec a,\vec b$ 线性相关；
当n=3时，有 $\vec 0,\vec a,\vec b,\vec a+\vec b,\vec b+\vec c,\vec a+\vec c,\vec a+\vec b+\vec c$ 这8个向量与 $\vec a,\vec b,\vec c$ 线性相关； $......$

所以，对于每个i，会有 ${2^i}$ 个向量线性相关，所以有 ${2^n-2^i}$ 个向量线性独立（无关）。
那么就很好做了，先得出一个easy的结论： $P=\frac{2^n-2^i}{2^n}$ 。接着推导：

（最后一步是将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;
}