1 条题解
-
0
考虑那些点可以对 产生贡献。
操作对于一个数的本质使这样的:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1容易发现，行列是独立的，并且一个位置就是对应的行列的乘积。
因此只需要单独考虑行。
1 1 1 1 0 1 1 1 1 1 1 0 0 0 1发现了吗？这就是杨辉三角。
所以相当于 $A_{0,0}=A_{i,j}\times (C_{k}^{i}\times C_{k}^{j} \mod 2)$。
发现这个模二，可以用卢卡斯定理，实际上就是二进制下所有组合数的乘积。
所以 时， 会对答案产生贡献。
然后发现这东西就是高维前缀和，直接维护就好了。
但发现这个 非常的大，考虑 很小，所以大的位可以约掉。
代码
#include <bits/stdc++.h> using namespace std; int f[(1<<23)+5]; void init(int n, int m, int q, int aw, int kw, const vector<vector<int> > &a) { for(int i=0;i<n;i++) for(int j=0;j<m;j++) f[i|j]^=a[i][j]; for(int p=0;p<=23;p++) for(int i=0;i<1<<23;i++) if(i&(1<<p))f[i]^=f[i-(1<<p)]; } int query(int k) {k%=(1<<23);return f[k];} struct xorShift128Plus { unsigned long long k1, k2; unsigned long long gen() { register unsigned long long k3 = k1, k4 = k2; k1 = k4; k3 ^= k3 << 23; k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26); return k2 + k4; } int gen(int w) {return gen() >> (64 - w);} }; int main() { int n, m, q, aw, kw; xorShift128Plus rng; scanf("%d%d%d%d%d%llu%llu", &n, &m, &q, &aw, &kw, &rng.k1, &rng.k2); vector<vector<int> > a(n, vector<int>(m)); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) a[i][j] = rng.gen(aw); init(n, m, q, aw, kw, a); unsigned long long res = 0; for (int i = 1; i <= q; i++) res ^= (unsigned long long)i * query(rng.gen(kw)); printf("%llu\n", res); return 0; }
- 1
信息
- ID
- 70
- 时间
- 3000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者
-
houzhiyuan