1 条题解

  • 0
    @ 2026-8-12 21:57:26

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    typedef vector <LL> vi;
    constexpr int N = 5e3 + 5, mod = 1e9 + 7;
    int ksm(int a, int b) {
    	int ret = 1;
    	for (; b; b >>= 1, a = 1LL * a * a % mod) if (b & 1) ret = 1LL * ret * a % mod;
    	return ret;
    }
    int n, r, f[N][N], pw[N];
    bitset <N> a[N];
    int main() {
    	ios :: sync_with_stdio(false);
    	cin.tie(nullptr);
    
    	cin >> n;
    	for (int i = 1; i <= n; i++) {
    		for (int j = 1; j <= n; j++) {
    			int x;
    			cin >> x, a[i][j] = x;
    		}
    	}
    	r = 0;
    	for (int i = 1; i <= n; i++) {
    		int p = r + 1, k = p;
    		while (a[k][i] == 0 && k <= n) k++;
    		if (k == n + 1) continue;
    		if (k > p) swap(a[k], a[p]);
    		for (int j = p + 1; j <= n; j++) if (a[j][i]) a[j] ^= a[p];
    		r++; 
    	}
    	pw[0] = 1;
    	for (int i = 1; i <= n; i++) pw[i] = 2LL * pw[i - 1] % mod;
    	f[0][0] = 1;
    	for (int i = 1; i <= n; i++) {
    		for (int j = 0; j <= i; j++) {
    			f[i][j] = 1LL * f[i - 1][j] * pw[j] % mod;
    			if (j >= 1) f[i][j] = (f[i][j] + 1LL * f[i - 1][j - 1] * (pw[n] + mod - pw[j - 1]) % mod) % mod;
    		}
    	}
    	int ans = 0;
    	for (int i = r; i <= n; i++) ans = (ans + 1LL * f[n][i] * f[i][r] % mod * ksm(pw[n - i], n) % mod) % mod;
    	ans = 1LL * ans * ksm(f[n][r], mod - 2) % mod;
    	cout << ans << "\n"; 
    	return 0;
    } 
    
    
    • 1

    信息

    ID
    10098
    时间
    2000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    5
    已通过
    2
    上传者