题源牛客2020暑假多校第六场B题。

题目大意

对于$n$个$n$维Binary Vector，求向量组线性无关的概率。

推导过程

由于其线性无关，易得公式：

$f_{N}=\prod_{i=0}^{N-1}\frac{2^N-2^i}{2^N}$

$f_{N-1}=\prod_{i=0}^{N-2}\frac{2^{N-1}-2^i}{2^{N-1}}$

$f_{N}=\frac{2^{N-1}*(2^{N}-1)}{2^{N-1}2^{N}}\prod_{i=0}^{N-2}\frac{2^{N-1}-2^i}{2^{N-1}}$

$=\frac{2^N-1}{2^N}f_{N-1}$

用$O(n)$的预处理打表可实现$O(1)$的查询。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const ll MOD = 1e9 + 7;
const int N = 2e7 + 1;
 
int t;
int n;
ll f[N];
ll ans[N];
ll pow_2[N];
  
int main() {
    scanf("%d", &t);
 
    pow_2[1] = 2;
    for ( int i = 2; i <= 2e7; ++i )
        pow_2[i] = pow_2[i - 1] * 2 % MOD;
    f[1] = 500000004;
    ans[1] = 500000004;
    ll inv_2 = 500000004;
    ll inv = inv_2;
    for ( int i = 2; i <= 2e7; ++i ) {
        inv = inv * inv_2 % MOD;
        f[i] = f[i - 1] * (pow_2[i] - 1) % MOD * inv % MOD;
 
        ans[i] = f[i] ^ ans[i - 1];
    }
 
    while ( t-- ) {
        scanf("%d", &n);
 
        printf("%lld\n", ans[n]);
    }
 
    return 0;
}