[UOJ310] 黎明前的巧克力
Sol
某比賽搬了這題。
首先選擇兩個不交非空子集且異或和為0的方案數,等價於選擇一個異或和為0的集合,並把它分成兩部分的方案數。
這顯然可以DP來算,設\(f[i][j]\) 表示前\(i\) 個數異或和為\(j\)的方案數,那麼轉移就是
\(f[i][j]=f[i-1][j]+2\cdot f[i-1][j\;\text{xor}\;a[i]]\)
如果設\(b_i[0]=1,b_i[a[i]]=2,b_i[j]=0\) ,那麼這個轉移就是求\(f\) 與\(b_i\;\text{xor}\) 卷積的過程,可以用FWT優化,但是複雜度似乎更爆炸了。
如果我們可以把每個\(b\) FWT之後的結果都求出來並乘在一起,最後在對應位置乘到\(f\) 上,再把\(f\) IFWT回去不就好了嘛!
如果把\(b_i\) 陣列FWT之後的結果打印出來,會發現所有位置不是\(3\) 就是\(-1\) ,大概是因為這個\(2\) 對每一項的貢獻要麼是\(2\) 要麼是\(-2\) 。
我們可以先把\(b_i\) 陣列整個加起來,對它做一次FWT。
因為FWT的和等於和的FWT。對於FWT之後的第\(i\) 項\(s\) ,設這位有\(x\) 個數為\(-1\) ,那麼就有\(n-x\) 個數為\(3\) ,且\(3(n-x)-x=s\) ,解得\(x=\large \frac{3n-s}4\) 。那麼FWT之後這一項的值就是\((-1)^x3^{n-x}\) 。
然後乘到\(f\) 上再IFWT回去就行了。
(uoj被卡了我不知道這程式碼能過否
Code
#include<set> #include<map> #include<queue> #include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef double db; typedef long long ll; const int N=4098; const int maxn=4096; const int mod=998244353; const int inv2=(mod+1)/2; int n,f[N],b[N],po[N]; void Mul(int &x,int y){x=1ll*x*y%mod;} int mul(int x,int y){return 1ll*x*y%mod;} void Dec(int &x,int y){x=x-y<0?x+mod-y:x-y;} int dec(int x,int y){return x-y<0?x+mod-y:x-y;} void Inc(int &x,int y){x=x+y>=mod?x+y-mod:x+y;} int inc(int x,int y){return x+y>=mod?x+y-mod:x+y;} int ksm(int a,int b=mod-2,int ans=1){ while(b){ if(b&1) ans=mul(ans,a); a=mul(a,a); b>>=1; } return ans; } void fwt(int *f,int opt){ for(int mid=1;mid<maxn;mid<<=1){ for(int R=mid<<1,j=0;j<maxn;j+=R){ for(int k=0;k<mid;k++){ int x=f[j+k],y=f[j+k+mid]; f[j+k]=inc(x,y),f[j+k+mid]=dec(x,y); if(opt<1) Mul(f[j+k],inv2),Mul(f[j+k+mid],inv2); } } } } signed main(){ scanf("%d",&n); f[0]=1; fwt(f,1); po[0]=1; for(int i=1;i<=n;i++) po[i]=mul(po[i-1],3); for(int x,i=1;i<=n;i++) scanf("%d",&x),b[0]++,b[x]+=2; fwt(b,1); for(int i=0;i<maxn;i++){ int x=(n*3-b[i])/4; Mul(f[i],x&1?mod-po[n-x]:po[n-x]); } fwt(f,-1); printf("%d\n",dec(f[0],1)); }