Cptraser/ 三月 11, 2019/ 2019.3/ 0 comments

题面传送门

观察题意可以发现,只要A+B的异或和为0,那么只要一个人随便取,另一个人取补集即可,这样做的贡献为2^{|A+B|}-1

f_{i,j}表示前i个点,异或和为j的方案数:

    \[f_{i,j}=f_{i-1,j}+2 * f_{i-1,j\oplus a_i}\]

g_{ai},表示f递推的系数,那么g_{ai}(0)=1g_{ai}(a_i)=2

打表可以发现,FWT后每一位要不是-1就是3

那么设最后为若干个3-1相乘:

    \[3x-(n-x)=\sum FWT(g_{ai})[k]=s_{k}\]

那么x=\frac{s_k+n}{4}

基于FWT的线性性质,s_k=\sum FWT(\sum g_{ai})[k],所以我们只要做一遍FWT即可。

计算出这一位的值3^x * (-1)^{n-x},再IFWT即可,注意减去空集,即答案为F[0]-1

#include <cstdio>
#include <algorithm>
using namespace std;

inline char tc(){
    static char tr[10000],*A=tr,*B=tr;
    return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x){
    char c;for(;(c=tc())<48||c>57;);
    for(x=c-'0';(c=tc())>47&&c<58;x=(x<<1)+(x<<3)+c-'0');
}

const int Maxn=1<<20|5,Mod=998244353,inv2=(Mod+1)>>1,inv4=1ll*inv2*inv2%Mod;

int N,A[Maxn],F[Maxn],G[Maxn],Len=1,th[Maxn],x,T;

void FWT(int *A,int Opt){
    for(int i=1;i<Len;i<<=1)
        for(int j=0;j<Len;j+=(i<<1))
            for(int k=0;k<i;k++){
                int x=A[j+k],y=A[i+j+k];
                A[j+k]=(x+y)%Mod,A[i+j+k]=(x-y+Mod)%Mod;
                if(Opt<0)A[j+k]=1ll*A[j+k]*inv2%Mod,A[i+j+k]=1ll*A[i+j+k]*inv2%Mod;
            }
}


int main()
{
    read(N);th[0]=F[0]=1;
    for(int i=1;i<=N;i++)read(x),T=max(T,x),G[0]+=1,G[x]+=2,th[i]=1ll*th[i-1]*3%Mod;
    while(Len<=T)Len<<=1;
    FWT(G,1),FWT(F,1);
    for(int i=0;i<Len;i++){
        int x=1ll*(G[i]+N)*inv4%Mod;
        F[i]=1ll*F[i]*th[x]*((N-x)&1?-1:1)%Mod;
    }FWT(F,-1);printf("%d\n",(F[0]-1+Mod)%Mod);
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*