子集卷积 有两个长度为 2n 的数列 a0,...,a2n−1 和 b0,...,b2n−1 . 求数列 c0,...,c2n−1 ，其中 cr= +卷积:
∑p⊆rap×br−p or卷积: ∑p,q[p or q=r]apbq and卷积: ∑p,q[p and q=r]apbq不标准或不对的地方欢迎指教:)
#include <set> #include <ctime> #include <queue> #include <cstdio> #include <bitset> #include <cctype> #include <bitset> #include <cstdlib> #include <cassert> #include <cstring> #include <iostream> #include <algorithm> #define inf (1<<30) #define INF (1ll<<62) #define fi first #define se second #define rep(x,s,t) for(register int x=s,t_=t;x<t_;++x) #define per(x,s,t) for(register int x=t-1,s_=s;x>=s_;--x) #define travel(x) for(int I=last[x],to;I&&(to=e[I].to);I=e[I].nxt) #define prt(x) cout<<#x<<":"<<x<<" " #define prtn(x) cout<<#x<<":"<<x<<endl #define pb(x) push_back(x) #define hash asfmaljkg #define rank asfjhgskjf #define y1 asggnja #define y2 slfvm using namespace std; typedef long long ll; typedef pair<int,int> ii; template<class T>void sc(T &x){ int f=1;char c;x=0; while(c=getchar(),c<48)if(c=='-')f=-1; do x=x*10+(c^48); while(c=getchar(),c>47); x*=f; } template<class T>void nt(T x){ if(!x)return; nt(x/10); putchar(x%10+'0'); } template<class T>void pt(T x){ if(x<0)putchar('-'),x=-x; if(!x)putchar('0'); else nt(x); } template<class T>void ptn(T x){ pt(x);putchar('\n'); } template<class T>void pts(T x){ pt(x);putchar(' '); } template<class T>inline void Max(T &x,T y){if(x<y)x=y;} template<class T>inline void Min(T &x,T y){if(x>y)x=y;} int n; const int maxn=17; const int mod=1e9+7; int a[1<<maxn],b[1<<maxn]; int w[1<<maxn]; inline void mop(int &a,int b){ if((a+=b)>=mod)a-=mod; } void ormul(int *a,int *b,int *c,int n){ static int A[1<<maxn],B[1<<maxn]; rep(i,0,1<<n)A[i]=a[i],B[i]=b[i]; rep(i,0,n)rep(j,1,1<<n) if(j>>i&1){ mop(A[j],A[j^1<<i]); mop(B[j],B[j^1<<i]); } rep(i,0,1<<n)c[i]=A[i]*B[i]; rep(i,0,n)rep(j,1,1<<n) if(j>>i&1)mop(c[j],mod-c[j^1<<i]); }//O(n*2^n) void plusmul(int *a,int *b,int *c,int n){ static int A[maxn+1][1<<maxn]; static int B[maxn+1][1<<maxn]; static int C[maxn+1][1<<maxn]; rep(i,0,n+1)rep(j,0,1<<n) if(w[j]==i) A[i][j]=a[j], B[i][j]=b[j]; else A[i][j]=B[i][j]=0; rep(i,0,n)rep(j,0,1<<n)if(j>>i&1) rep(k,0,w[j]) mop(A[k][j],A[k][j^1<<i]), mop(B[k][j],B[k][j^1<<i]); rep(i,0,1<<n)rep(j,0,n+1){ C[j][i]=0; rep(k,0,j+1) mop(C[j][i],(ll)A[k][i]*B[j-k][i]%mod); } rep(i,0,n)rep(j,0,1<<n)if(j>>i&1) rep(k,0,n+1) mop(C[k][j],mod-C[k][j^1<<i]); rep(i,0,1<<n)c[i]=C[w[i]][i]; }//O(n^2*2^n) void pulsmul(int *a,int *b,int *c,int n){ rep(i,0,1<<n){ c[i]=0; for(int j=i;;j=(j-1)&i){ mop(c[i],(ll)*a[j]*b[i-j]%mod); if(!j)break; } } }//O(3^n) int main(){ // freopen("pro.in","r",stdin); // freopen("chk.out","w",stdout); sc(n); rep(i,1,1<<n)w[i]=w[i>>1]+(i&1); rep(i,0,1<<n)sc(a[i]); rep(i,0,1<<n)sc(b[i]); // plusmul(a,b,a,n);// // ormul(a,b,a,n);// rep(i,0,1<<n){ pt(a[i]); putchar(" \n"[i==t_-1]); } return 0; }