一道矩阵变换型 adhoc 好题

· · 个人记录

题目描述

n\times m \le 5\times 10^6,q \le 5\times 10^7

解题思路

一看这题就是不好做的 adhoc，先打表找一找规律。 

11000 10100 11110 10001
11000 00000 11110 00000
00000 10100 11110 00000
00000 00000 11110 00000
00000 00000 00000 10001 ...

发现 2 的幂都是占四个角，每个角都是 k-2^x 的形态。于是往二进制方向猜性质。
发现每个位置被选到当且仅当 i \& k = i 且 j \& k=j，合并一下 (i\mid j)\& k=i\mid j。
显然做到 max(n,m) 的二进制最高位就可以了，更高位没有意义。上面的式子可以用高维前缀和算出来，复杂度 O(max(n,m)\log max(n,m)+q)。

代码分析

#include <bits/stdc++.h>
using namespace std;
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); }
}rng;
int n, m, q, aw, kw, sum, ans[10000005],L;
void init(){
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            ans[i|j]^=rng.gen(aw);//只需要考虑i|j即可
    for(L=1;L<max(n,m);L<<=1);//最高位
    for(int i=1;i<L;i<<=1)
        for(int j=0;j<L;j+=(i<<1))//高维前缀和的枚举
            for(int k=0;k<i;k++)//jk拼起来复杂度O(n)
                ans[i+j+k]^=ans[j+k];
}
int query(int K){
    return ans[K&(L-1)];//控制位数
}
int main() {
    freopen("kk.in","r",stdin);
    freopen("kk.out","w",stdout);
    scanf("%d%d%d%d%d%llu%llu",&n,&m,&q,&aw,&kw,&rng.k1,&rng.k2);
    init();
    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);
    cerr<<(1.0*clock()/CLOCKS_PER_SEC)<<endl;
    return 0;
}