正文索引 [隐藏]

传送门

题目大意

有一个n 维向量空间，从这里面拿出n个01向量，设fn为选出的这n个01向量相互线性独立的概率，求 f1^ f2^…^ fn 的值。

思路

有n个向量，它们都线性无关，所以它们的空间秩也是n。每次随机的向量都会加入之前的向量空间，那么每一个向量都一定不属于之前的空间，则一共有2n个向量。

观察规律不难得到对于每个i，都有2i个向量线性相关，那么反之则有2n-2i个向量线性无关。那么有：

递推计算出每个f就行了。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e7 + 10;
const ll MOD = 1e9 + 7;
const ll INF = 500000004;

int	t;
ll n, f[N];

int main()
{
	f[1] = INF;
	ll x = INF, y = 1;
	
	for ( int i = 2; i <= N; i++ )
	{
		x = x * f[1] % MOD;
		y = (y * 2 + 1) % MOD;
		f[i] = (f[i - 1] * y) % MOD * x % MOD;
	}
	
	for ( int i = 2; i < N; i++ )
		f[i] ^= f[i - 1];
	
	cin >> t;
	while ( t-- )
	{
		scanf("%lld", &n);
		printf("%lld\n", f[n]);
	}
	
	return 0;
}