还是补全一下科技树吧...之后可能就专心刷刷题？
虽然感觉我的科技树连开始的一层都没点全。。。
FWT 可以用来解决多项式的位运算卷积，也就是对于两个多项式 $A,B$ ，求一个 $C$ 满足 $C_k = sumlimits_{i=1}^nsumlimits_{j=1}^n[ioplus j == k]A_i imes B_j$
常见的有 $and,or,xor$ 卷积
式子就不推了，放个结论吧
令 $A$ 为一个 $2^n$ 维向量
设 $A_0$ 为 $A$ 的前 $2^{n-1}$ 维组成的向量， $A_1$ 为 $A$ 的后 $2^{n-1}$ 维组成的向量
则
对于 or 卷积：
$$FWT(A)=
egin{cases}
(FWT(A_0),FWT(A_0) + FWT(A_1))& ext{n>0}\
A& ext{n=0}
end{cases}$$
顺便，or 的 FWT 相当于对于每个非空集合求了子集和
对于 and 卷积：
$$FWT(A)=
egin{cases}
(FWT(A_0) + FWT(A_1),FWT(A_1))& ext{n>0}\
A& ext{n=0}
end{cases}$$
对于 xor 卷积：
$$FWT(A)=
egin{cases}
(FWT(A_0) + FWT(A_1),FWT(A_0) - FWT(A_1))& ext{n>0}\
A& ext{n=0}
end{cases}$$
#include<bits/stdc++.h> #define LL long long using namespace std; namespace IO{ const int BS=(1<<23)+5; int Top=0; char Buffer[BS],OT[BS],*OS=OT,*HD,*TL,SS[20]; const char *fin=OT+BS-1; char Getchar(){if(HD==TL){TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);} return (HD==TL)?EOF:*HD++;} void flush(){fwrite(OT,1,OS-OT,stdout);} void Putchar(char c){*OS++ =c;if(OS==fin)flush(),OS=OT;} void write(int x){ if(!x){Putchar('0');return;} if(x<0) x=-x,Putchar('-'); while(x) SS[++Top]=x%10,x/=10; while(Top) Putchar(SS[Top]+'0'),--Top; } int read(){ int nm=0,fh=1; char cw=Getchar(); for(;!isdigit(cw);cw=Getchar()) if(cw=='-') fh=-fh; for(;isdigit(cw);cw=Getchar()) nm=nm*10+(cw-'0'); return nm*fh; } } using namespace IO; const int maxn = 200010,mod = 998244353,inv2 = 499122177; int n,m,a[maxn],b[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 < 0)x += mod;return x;} inline int skr(int x,int t) { int res = 1; while(t) { if(t & 1)res = 1LL * res * x % mod; x = 1LL * x * x % mod; t = t >> 1; }return res; } inline void fwt(int *a,int n,int t,int f)//1:or , 2:and , 3:xor { for(int i=1;i<n;i<<=1) { for(int j=0,p=i<<1;j<n;j+=p) { for(int k=0;k<i;++k) { int x = a[j + k],y = a[i + j + k]; if(t == 1) { if(f == 1) a[i + j + k] = inc(x,y); else a[i + j + k] = dec(y,x); } else if(t == 2) { if(f == 1) a[j + k] = inc(x,y); else a[j + k] = dec(x,y); } else if(t==3) { if(f == 1) a[j + k] = inc(x,y),a[i + j + k]=dec(x,y); else a[j + k] = 1LL * inc(x,y) * inv2 % mod,a[i + j + k] = 1LL * dec(x,y) * inv2 % mod; } } } } } int main() { int t = read();n = read(),m = read(); int l = max(n,m),L = 0,bs = 1; for(;bs < l;bs <<= 1)L++; for(int i=0;i<=n;i++)a[i] = read(); for(int i=0;i<=m;i++)b[i] = read(); fwt(a,bs,t,1);fwt(b,bs,t,1); for(int i=0;i<bs;i++)a[i] = 1LL * a[i] * b[i] % mod; fwt(a,bs,t,-1); for(int i=0;i<bs;i++)write(a[i]),Putchar(' '); flush(); }
WC2018 州区划分
有一个无向图，你要把它划分成 k 个州，要求每个州内不能存在欧拉回路，每个州的满意度是 $i$ 州的权值和除以前 $i$ 州的权值和 ，一个划分方案的满意度是所有州满意度的乘积，求所有划分方案满意度之和，膜 998244353
$n leq 21$
sol：
记 $sig_S=sumlimits_{i in S}w_i imes [州内没有欧拉回路]$
显然是一个子集 dp：
$f_{S} = frac{1}{sig_S}sumlimits_{Tsubseteq S}f_{T} imes sig_{S-T}$
然后发现这是一个子集卷积，一般是枚举一下集合大小，然后直接卷
HAOI2015 按位或
一开始你有一个数字 $0$ ，每秒你有 $P_i$ 的概率得到一个$in [0,2^n-1]$数字 $i$，与你现在的数字进行按位或，求期望多少秒能得到 $2^n-1$
$n leq 20$
sol：
先最值反演
然后就是对于每个子集 $T$ 要求 $E(min{T})$
发现只要有一位异或上了就可以了，那就是 $E(min{T}) = frac{1}{sumlimits_{s ∩ T eq emptyset}P_s}$
现在就是对于每个 $T$ 要求所有与 $T$ 有交的集合权值和
发现有交的不好求，没交的就是 $T$ 所有补集的子集，用 FWT 预处理子集和就行了
（其实不 FWT 也行，但这毕竟是一篇 FWT 博客