题解：CF1906K Deck-Building Game

_Ch1F4N_ · 2025-03-28 17:34:30 · 题解

问题等价于先选出一个异或和为 0 的子集，再选出这个集合的一个子集。

可以通过生成函数刻画答案，不妨令 a \times x^p \times b \times x^q = a \times b \times x^{p \oplus q}。答案就是多项式 \prod_{i=1}^n (1+2 \times x^{A_i}) 的 x^0 项的系数。

我们考察下 (1+2 \times x^{A_i}) 做异或 FWT 运算之后会得到什么，由于异或 FWT 的定义之一是 \text{FWT}(A)_i = \sum_j (-1)^{\text{popc}(i \cap j)} \times A_j，所以得到的数组第 j 位会因为 popc(i \cap j) 的奇偶性为 -1 或者 3。

不妨设 \text{FWT} \prod_{i=1}^n (1+2 \times x^{A_i}) 第 i 位被贡献了 t_i 个 -1，第 i 位的值就是 (-1)^{t_i} \times 3^{n - t_i}。求出每一位的值后，做一遍逆异或 FWT 就能求出答案。

下面考虑求解 t_i 的值，考虑这样一个算法：记序列 F = \sum \text{FWT}(1+2 \times 2^{A_i})，有 F_i = -t_i + 3 \times (n-t_i)。也就是如果能求出 F 序列，就能求出 t_i。

根据 FWT 的线性性，F = \text{FWT} \sum (1+2 \times x^{A_i})，于是可以在 O(n+V \log V) 的时间复杂度内求出答案。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
const int maxn = (1<<20);
int a[maxn],n;
void fwt_xor(int *f,int x=1){
    for(int o=2,k=1;o<=maxn;o<<=1,k<<=1){
        for(int i=0;i<maxn;i+=o){
            for(int j=0;j<k;j++){
                int a=f[i+j];
                int b=f[i+j+k];
                f[i+j]=(a+b)%mod;
                f[i+j+k]=(a+mod-b)%mod;
                f[i+j]=f[i+j]*x%mod,f[i+j+k]=f[i+j+k]*x%mod;
            }
        }
    }
}
int b[maxn];
int c[maxn];
int qpow(int a,int b){
    if(b==0) return 1;
    if(b==1) return a;
    int res=qpow(a,b/2);
    res=res*res%mod;
    if(b%2==1) res=res*a%mod;
    return res;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],b[0]++,b[a[i]]+=2;
    fwt_xor(b);
    for(int i=0;i<maxn;i++) b[i]=((3*n+mod-b[i])%mod)/4;
    for(int i=0;i<maxn;i++) c[i]=qpow(mod-1,b[i])*qpow(3,n-b[i])%mod;
    fwt_xor(c,(mod+1)/2);
    cout<<c[0]<<"\n";
    return 0;
}