1 条题解

  • 0
    @ 2022-1-22 18:35:58

    考虑那些点可以对 A0,0A_{0,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)$。

    发现这个模二,可以用卢卡斯定理,实际上就是二进制下所有组合数的乘积。

    所以 (ij)k(i|j)\in k 时,Ai,jA_{i,j} 会对答案产生贡献。

    然后发现这东西就是高维前缀和,直接维护就好了。

    但发现这个 kk 非常的大,考虑 (ij)(i|j)很小,所以大的位可以约掉。


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