解析

完全可以當一道 DP 題而不是模板來做。
首先第一個條件： $i|j=k$ 比較簡單，直接上FWT板子即可。
考慮第二個條件：$i\&j=0$。若設 $|x|$ 表示二進制下 1 的個數，那么就有： $|i|+|j|=|k|$。
那么考慮設計dp：$d{p}_{i,j}$ 表示二進制有 $i$ 個 1，或運算結果為 $j$ 的答案。
就有 $$d{p}_{k,i|j}=\sum _p^k\sum _{i,j}{f}_{p,i}{g}_{k?p,j}$$
然后把 $n$ 個 $f,g$ 變換后 $n^2$ 暴力卷積成答案再變換回去。
總復雜度 $O(n^2{2}^n)$。

代碼

（陰間題卡longlong的常數…）

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } const int N=1e6+1e5; const int mod=1e9+9;int n,lim; inline int calc(int x){int res(0);while(x){++res;x-=x&-x;}return res; } inline void Or(int *x,int lim,int op){for(int l=1;l<lim;l<<=1){for(int st=0;st<lim;st+=l*2){for(int i=0;i<l;i++){if(op==1) (x[st+i+l]+=x[st+i])%=mod;else (x[st+i+l]+=mod-x[st+i])%=mod;}}}return; } int A[21][N],B[21][N],C[21][N]; void write(int x){if(x>9) write(x/10);putchar('0'+x%10);return; } signed main(){ #ifndef ONLINE_JUDGE//freopen("a.in","r",stdin);//freopen("a.out","w",stdout); #endifn=read();lim=(1<<n);for(int i=0;i<lim;i++) A[calc(i)][i]=read();for(int i=0;i<lim;i++) B[calc(i)][i]=read();for(int i=0;i<=n;i++) Or(A[i],lim,1);for(int i=0;i<=n;i++) Or(B[i],lim,1);/*for(int k=0;k<=n;k++){for(int i=0;i<=k;i++){for(int x=0;x<lim;x++) C[k][x]=(C[k][x]+A[i][x]*B[k-i][x])%mod;} }*/for(int i=0;i<=n;i++){for(int x=0;x<=lim;x++){if(!A[i][x]) continue;for(int j=0;j+i<=n;j++) C[i+j][x]=(C[i+j][x]+1ll*A[i][x]*B[j][x]%mod)%mod;}//debug("%d\n",i);}/*for(int i=0;i<=n;i++){for(int j=0;j<=i;j++){for(int k=0;k<lim;k++) C[i][k]=(C[i][k]+1ll*A[j][k]*B[i-j][k]%mod)%mod;}//debug("%d\n",i);}*/for(int i=0;i<=n;i++) Or(C[i],lim,-1);for(int i=0;i<lim;i++) write(C[calc(i)][i]),putchar(' ');//for(int i=0;i<lim;i++) printf("%d ",C[calc(i)][i]);return 0; } /* */

總結

以上是生活随笔為你收集整理的洛谷P6097：【模板】子集卷积（FWT）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。