快速沃尔什变换 FWT

也和FFT很像。

typedef long long ll;const int P=998244353;ll _n=ksm(2,P-2);/*op=1,2,3分别对应XOR,AND,OR*/void FWT(int n,ll a[],int f,int op){    for(int i=1;i
    
     <<=1){        for(int j=0;j
     
      <<1){            for(int k=0;k
     
    

练习

• 【51Nod1773】A国的贸易

---

快速子集变换 FST

//FWT加上类似背包DPvoid FST(int d[],int a[],int n){    for(int i=1;i
    
     >1]+(i&1);    for(int i=0;i
    

练习

• 【codeforces914G】Sum the Fibonacci