P13497 【MX-X14-T7】墓碑密码

· · 题解

有点不太像题了，感觉非常诡异，写之前真没觉得能过。

显然如果可以求出 dp_i 表示 S 中选出 i 个数异或和在 T 的方案数，那么就容易快速回答一次询问，就是 \sum_{i=0}^{|S|} dp_i\binom{\lfloor\frac{|S|-i}{2}\rfloor+|S|}{|S|}。

问题在于如何快速求出 dp_i。考虑 FWT，设集合幂级数 A=\prod_{a\in S}(1+yx^{a})，其中 y 这一元表示已选的数的个数，那么就是要求 \sum_{v\in T}[x^v]A。根据 FWT 那一套的理论，[x^a]FWT(A)=\sum_{i=0}^{2^L-1}(-1)^{|a\cap i|}A_i，[x^a]IFWT(A)=2^{-L}\sum_{i=0}^{2^L-1}(-1)^{|a\cap i|}A_i。

于是容易写出更加直接的答案：

2^{-L}\sum_{v\in T}\sum_{w=0}^{2^L-1}(-1)^{|w\cap v|} \prod_{a\in S} (1+y(-1)^{|w\cap a|})

计算上式也很简单，先对于每个 w 求出 \sum_{v\in T}(-1)^{|w\cap v|}。又因为 \prod_{a\in S} (1+y(-1)^{|w\cap a|}) 这一项本质上只有 |S| 种值，形如 (1+y)^k(1-y)^{|S|-k}，于是只需要求出对于每一种 k 的系数和即可，最后使用二项式定理暴力展开即可得到 dp_i。容易做到 \mathcal{O}((|S|+|T|)\max\{S_i,T_i\})。

由于 |S|,|T|\le 128，考虑用两个 64 位二进制数（拼成一个 128 位二进制数）去存当 w 固定时，|w\cap S_i| 的奇偶性，然后从小到大递推转移，转移容易做到线性，每次从删除最低位的状态转移即可。

但是这样子空间爆炸了，实际上也容易解决，枚举 w 的前 8 位是啥，那么就只需要开一个 2^{20} 的数组了。

最后回答询问有一些细节需要处理，如果每次暴力 \mathcal{O}(|S|) 算组合数，那么就是 \mathcal{O}(q|S|^2)。一种解决方法是直接预处理 5\times 10^8+|S| 以内的阶乘，由于本题不卡空间，所以开的下。另外一种就是注意到 \lfloor\frac{|S|-i}{2}\rfloor 的变化量是 \mathcal{O}(|S|) 的，所以每次暴力移动区间乘积也行，但是还是要算一个数的逆元，所以会带 log，好像过不去。

时间复杂度 \mathcal{O}(\max\{S_i,T_i\}+q|S|+|S|^3)。

给个部分代码，正常写就能直接过，常数很小。

int n,m,q,a[205],b[205],g[205],dp[205];
ull f1[(1<<20)+5],f2[(1<<20)+5],f3[(1<<20)+5],f4[(1<<20)+5],sta1[25],sta2[25],sta3[25],sta4[25];
int sf[50000205];
inline void solveit(int v){
    f1[0]=f2[0]=f3[0]=f4[0]=0;
    for(int i=0;i<min(64,n);i++)
        if(__builtin_popcountll(v&a[i])&1)f1[0]|=(1ull<<i);
    for(int i=64;i<n;i++)
        if(__builtin_popcountll(v&a[i])&1)f2[0]|=(1ull<<(i-64));
    for(int i=0;i<min(64,m);i++)
        if(__builtin_popcountll(v&b[i])&1)f3[0]|=(1ull<<i);
    for(int i=64;i<m;i++)
        if(__builtin_popcountll(v&b[i])&1)f4[0]|=(1ull<<(i-64));
    for(int i=0;i<(1<<20);i++){
        if(i){
            int p=i^(i&-i),x=__builtin_ctz(i);
            f1[i]=(f1[p]^sta1[x]);
            f2[i]=(f2[p]^sta2[x]);
            f3[i]=(f3[p]^sta3[x]);
            f4[i]=(f4[p]^sta4[x]);  
        }
        int c=__builtin_popcountll(f1[i])+__builtin_popcountll(f2[i]);
        int c2=__builtin_popcountll(f3[i])+__builtin_popcountll(f4[i]);
        int v=dec(m,2*c2);
        g[c]=add(g[c],v);
    }
}
inline void solve(){
    gi(n),gi(m);
    for(int i=0;i<n;i++)gi(a[i]);
    for(int i=0;i<m;i++)gi(b[i]);
    for(int i=0;i<20;i++){
        for(int j=0;j<min(64,n);j++)if((1<<(i+8))&a[j])sta1[i]|=(1ull<<j);
        for(int j=64;j<n;j++)if((1<<(i+8))&a[j])sta2[i]|=(1ull<<(j-64));
    }
    for(int i=0;i<20;i++){
        for(int j=0;j<min(64,m);j++)if((1<<(i+8))&b[j])sta3[i]|=(1ull<<j);
        for(int j=64;j<m;j++)if((1<<(i+8))&b[j])sta4[i]|=(1ull<<(j-64));
    }
    for(int w=0;w<(1<<8);w++)solveit(w);
    int xs=qkpow((1<<28),mod-2);
    for(int i=0;i<=n;i++){
        for(int j=0;j<=i;j++){
            for(int k=0;k<=n-i;k++){
                int v=1ll*binom(i,j)*binom(n-i,k)%mod*g[i]%mod;
                if(j&1)dp[j+k]=dec(dp[j+k],v);
                else dp[j+k]=add(dp[j+k],v);
            }
        }
    }
    gi(q);
    while(q--){
        int N;
        gi(N);
        int res=0;
        for(int i=0;i<=n;i++){
            if(N>=i){
                int lim=(N-i)/2;
                int pro=1ll*fac[lim+n]*inv[lim]%mod;
                res=add(res,1ll*pro*inv[n]%mod*dp[i]%mod);
            }
        }
        pi(1ll*res*xs%mod);
    }
}