[UOJ310]黎明前的巧克力

题解

作业部落

评论地址

TAG：FWT

题意

在集合中选出任意多数，使得异或和为$0$，再将其分为两个有区别的可空集合的方案数（两集合不能都为空）

题解

考虑生成函数
如果选出一个异或和为$0$的集合大小为$k$，那么对答案的贡献就是$2^k$，于是把系数置为$2$
假设$n$个数的生成函数为$2x^{a[i]}$，分别为$A,B,C...$
那么答案就是$(A*B)[0],(B*C)[0],(A*B*C)[0]...$（异或卷积）
我们可以把每个生成函数的$0$次项置为$1$，那么答案就直接是$(A*B*C...)[0]$

就应该是$Ans=FWT(A)*FWT(B)*FWT(C)...$（每一位对应乘）
然后再把$Ans$给$UFWT$回来就是答案了
由于$FWT$的可加性（证明戳我）

$FWT(A+B)=FWT(A)+FWT(B)$

而且每个多项式都很特殊，$0$位上为$1$会对每一位做贡献，$a[i]$位为$2$会对一些位做$2$的贡献对另一些位做$-2$的贡献（因为是异或卷积所以每一位的数$FWT$后都会对所有的位造成影响），由此每一位要么为$-1$要么为$3$
所以按位加，共$n$个多项式，最后的值为$val$，则$3$的个数为$x$，$3*x+(-1)*(n-x)=val$，可以得到该位上$3$的总个数
最后是要乘起来的，所以$-1$只是变符号，$(-1)^{n-x}3^x$就是$Ans$的该位的值了，最后$UFWT$回来$Ans[0]-1$即为答案（多算了全是空集的一种情况）

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int read()
{
    char ch=getchar();int h=0,t=1;
    while((ch>'9'||ch<'0')&&ch!='-') ch=getchar();
    if(ch=='-') t=-1,ch=getchar();
    while(ch>='0'&&ch<='9') h=h*10+ch-'0',ch=getchar();
    return h*t;
}
const int mod=998244353;
const int N=1<<21;
const int inv=499122177;
int n,A[N],B[N],bit3[N],l;
void FWT_xor(int *P,int op)
{
    for(int i=1;i<l;i<<=1)
        for(int j=0,p=i<<1;j<l;j+=p)
            for(int k=0;k<i;k++)
            {
                int X=P[j+k],Y=P[j+k+i];
                P[j+k]=1ll*(X+Y)%mod*op%mod;
                P[j+k+i]=1ll*((X-Y)%mod+mod)*op%mod;
            }
}
int main()
{
    n=read();A[0]=n;bit3[0]=1;int mx=0;
    for(int i=1;i<=n;i++) bit3[i]=bit3[i-1]*3ll%mod;
    for(int i=1,x;i<=n;i++) A[x=read()]+=2,mx=max(mx,x);
    for(l=1;l<=mx;l<<=1);
    FWT_xor(A,1);
    for(int i=0;i<l;i++)
    {
        int x=(3ll*n-A[i]+mod)*inv%mod*inv%mod;
        A[i]=bit3[n-x]; if(x&1) A[i]=mod-A[i];
    }
    FWT_xor(A,inv);
    printf("%d\n",(A[0]-1+mod)%mod);
}