写起来和fft很像,这里放个板子.
代码:
#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<map> #include<algorithm> #include<cstring> using namespace std; #define duke(i,a,n) for(register int i = a;i <= n;i++) #define lv(i,a,n) for(register int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; typedef long long ll; typedef double db; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } template <class T> void write(T x) { if(x < 0) putchar('-'), x = -x; if(x >= 10) write(x / 10); putchar('0' + x % 10); } #define N 1 << 21 | 3 const int mod = 998244353; int lim,base; int a[N],b[N],c[N]; inline int mlt(int x,int y) { return x * 1ll * y % mod; } inline int mo(int x,int y) { if(x + y >= mod) return x + y - mod; if(x + y < 0) return x + y + mod; return x + y; } inline int d2(int x) { return (x & 1) ? (x + mod) >> 1 : x >> 1; } void fwt(int *a,int d,int op) { for(int i = 1;i < lim;i <<= 1) { for(int k = 0;k < lim;k += (i << 1)) { for(int l = 0;l < i;l++) { if(op == 0) a[k + l + i] = mo(a[k + l + i],d * a[k + l]); else if(op == 1) a[k + l] = mo(a[k + l],d * a[k + l + i]); else { int nx = a[k + l],ny = a[k + l + i]; a[k + l] = mo(nx,ny),a[k + l + i] = mo(nx,-ny); if(d == -1) a[k + l] = d2(a[k + l]),a[k + l + i] = d2(a[k + l + i]); } } } } } int main() { read(base); lim = 1 << base; duke(i,0,lim - 1) read(a[i]); duke(i,0,lim - 1) read(b[i]); for(int op = 0;op <= 2;op ++) { fwt(a,1,op); fwt(b,1,op); for(int i = 0;i < lim;i++) { c[i] = mlt(a[i],b[i]); } fwt(a,-1,op); fwt(b,-1,op); fwt(c,-1,op); duke(i,0,lim - 1) { printf("%d ",c[i]); } puts(""); } return 0; }