求不相交集合并卷积
sol：
集合并卷积？看我 FWT！
交一发，10 以上的全 T 了
然后经过参考别人代码认真比对后发现我代码里有这么一句话：
rep(s, , MAXSTATE) rep(i, , n) rep(j, , n - i) h[i + j][s] = inc(h[i + j][s], mul(f[i][s], g[j][s]));
把它改成
rep(i, , n) rep(j, , n - i) rep(s, , MAXSTATE) h[i + j][s] = inc(h[i + j][s], mul(f[i][s], g[j][s]));
就过了...
有理有据地分析一波，上面那种写法会访问 $O(2^n)$ 次不连续的空间，下面那种写法只有 $O(n)$ 次
写出来主要还是提醒自己以后数组访问尽量连续吧...
orz
#include <bits/stdc++.h>
#define LL long long
#define rep(i, s, t) for (register int i = (s), i##end = (t); i <= i##end; ++i)
#define dwn(i, s, t) for (register int i = (s), i##end = (t); i >= i##end; --i)
using namespace std;
namespace IO{
const int BS=(<<)+; int Top=;
char Buffer[BS],OT[BS],*OS=OT,*HD,*TL,SS[]; const char *fin=OT+BS-;
char Getchar(){if(HD==TL){TL=(HD=Buffer)+fread(Buffer,,BS,stdin);} return (HD==TL)?EOF:*HD++;}
void flush(){fwrite(OT,,OS-OT,stdout);}
void Putchar(char c){*OS++ =c;if(OS==fin)flush(),OS=OT;}
void write(int x){
if(!x){Putchar('');return;} if(x<) x=-x,Putchar('-');
while(x) SS[++Top]=x%,x/=;
while(Top) Putchar(SS[Top]+''),--Top;
}
int read(){
int nm=,fh=; char cw=Getchar();
for(;!isdigit(cw);cw=Getchar()) if(cw=='-') fh=-fh;
for(;isdigit(cw);cw=Getchar()) nm=nm*+(cw-'');
return nm*fh;
}
}
using namespace IO;
const int mod = 1e9 + , maxn = ( << );
int n;
int f[][maxn], g[][maxn], h[][maxn], bt[maxn];
inline int inc(int x, int y) {
x += y;
if (x >= mod)
x -= mod;
return x;
}
inline int dec(int x, int y) {
x -= y;
if (x < )
x += mod;
return x;
}
inline int mul(int x, int y) { return 1LL * x * y % mod; }
void fwt(int *a, int n, int f) {
for (int i = ; i < n; i <<= ) {
for (int j = ; j < n; j += (i << )) {
for (int k = ; k < i; k++) {
int x = a[j + k], y = a[j + k + i];
if (f == )
a[j + k + i] = inc(x, y);
else
a[j + k + i] = dec(y, x);
}
}
}
}
int main() {
n = read();
int MAXSTATE = ( << n) - ;
rep(s, , MAXSTATE) bt[s] = __builtin_popcount(s);
rep(s, , MAXSTATE) f[bt[s]][s] = read();
rep(s, , MAXSTATE) g[bt[s]][s] = read();
rep(s, , n) fwt(f[s], MAXSTATE + , ), fwt(g[s], MAXSTATE + , );
rep(i, , n) rep(j, , n - i) rep(s, , MAXSTATE) h[i + j][s] = inc(h[i + j][s], mul(f[i][s], g[j][s]));
//rep(s, 0, MAXSTATE) rep(i, 0, n) rep(j, 0, n - i) h[i + j][s] = inc(h[i + j][s], mul(f[i][s], g[j][s]));
rep(s, , n) fwt(h[s], MAXSTATE + , -);
rep(s, , MAXSTATE) write(h[bt[s]][s]), Putchar(' ');
Putchar('\n'); flush();
}