前言

学多项式怎么能错过\(FWT\)呢，然而这真是个毒瘤的东西，蒟蒻就只会背公式了\(\%>\_<\%\)

或卷积

\[\begin{aligned}\\ tf(A) = (tf(A_0), tf(A_1) + tf(A_0))\\ utf(A) = (utf(A), utf(A_1) - utf(A_0))\\ \end{aligned}\]

与卷积

\[\begin{aligned}\\ tf(A) = (tf(A_0) + tf(A_1), tf(A_1))\\ utf(A) = (utf(A_0) - utf(A_1), utf(A_1))\\ \end{aligned}\]

异或卷积

\[\begin{aligned}\\ tf(A) = (tf(A_0) + tf(A_1), tf(A_0) - tf(A_1))\\ utf(A) = (\frac{utf(A_0) + utf(A_1)}{2}, \frac{utf(A_0) - utf(A_1)}{2})\\ \end{aligned}\]

Code

习惯写递归的非递归本来也不会

#include
    
     typedef int LL;inline LL Read(){    LL x(0),f(1); char c=getchar();    while(c<'0' || c>'9'){        if(c=='-') f=-1; c=getchar();    }    while(c>='0' && c<='9'){        x=(x<<3)+(x<<1)+c-'0'; c=getchar();    }    return x*f;}const LL mod=998244353,maxn=1<<18,inv2=499122177;inline LL Pow(LL base,LL b){    LL ret(1);    while(b){        if(b&1) ret=1ll*ret*base%mod; base=1ll*base*base%mod; b>>=1;    }    return ret;}void Solve_or(LL n,LL *a,LL *b,LL *c){    n>>=1;    if(!n){        c[0]=1ll*a[0]*b[0]%mod;        return;    }    for(LL i=0;i
     
      >=1;    if(!n){        c[0]=1ll*a[0]*b[0]%mod;        return;    }    for(LL i=0;i
      
       >=1;    if(!n){        c[0]=1ll*a[0]*b[0]%mod;        return;    }    for(LL i=0;i