1 条题解
-
0

#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
- 上传者