FWT

一、処理する問題:
2つのシーケンス(A,B)が与えられ、シーケンス(C)が求められ、ここで(C_i=sumlimits_{joplus k=i}A_j*B_k)は演算である.
二、例を挙げる
我々は(FFT)の思想を用いて,まず(A,B)に対してシーケンス(FWT(A))と(FWT(B))を構築し,(FWT(C)_を満たすことを考慮する.i=FWT(A)_i*FWT(B)_i)、その後(FWT(C))から(C)に移行します.
演算例:
(k=imid j)がある場合、(i,j)は必ず(k)のサブセットです.
我々はまず(FWT(A)_を構築する.i=A'_i=\sum\limits_{i=i|j}A_j)は、(j)が(i)のサブセットであることを示す.
すると(C'_i=sumlimits_{i=i|(j|k)}C_{j|k}=\sum\limits_{i=i|j}A_j*\sum\limits_{i=i|k}B_k=A'_i*B'_i)即ち:(FWT(C)i=FWT(A)_i*FWT(B)_i\)
今どのように求めます(FWT(A)):
暴力は明らかに(O(n^2))の(各(i)に対して(j))であり、私たちは分治を考えている.
このとき我々は(A)を二つに分けて、シーケンス(A)の前半を(A_1)に、後半を(A_2)に示す.
このとき、(FWT(A)=merge(FWT(A_1)、FWT(A_1)+FWT(A_2))のうち、(merge)は2つのシーケンスを前後につなぎ合わせることを示し、(+)は各ビットを加算することを示す.
(FWT(A))の前半では、現在のバイナリの最上位が(0)であるため、(FWT(A_1))に等しい.
一方、(FWT(A))の後半については、まず(FWT(A_2))があるに違いないが、(A_1)の要素が(FWT(A))の後半に寄与することを考える.
我々は(len(A_1)=len(A_2)=l)とする.
では、(i,(i)と(i+l)は最上位にしか差がありませんが、私たちはすでに最上位に(1)の統計を入れました(FWT(A_2))、このとき(FWT(A)i)が残っているのは(FWT(A){i+l})欠落しているすべての(A_j).
そこで我々は(O(nlogn))を再帰的に分治して(FWT)を行うことができる.
私たちは(FWT(C))を求めた後、逆変換を行うので、(IFWT)はどうするか考えます.
実は(IFWT)は簡単で、私たちはさっきの(FWT)の過程に逆行すればいいのです.
\(IFWT(C)=merge(IFWT(C_1),IFWT(C_2)-IFWT(C_1))\)
三、普及
より広くは(oplus)の(FWT)は、(A'={sumlimits_{ioplus j=0}A_i*B_j,sumlimits_{ioplus j=1}A_i*B_j,...,sumlimits_{ioplus j=n-1}A_i*B_j})
次に、他の演算の(FWT)を求める方法を示します.
または演算と同様に、演算の求め方として(FWT(A)=merge(FWT(A_1)+FWT(A_2),FWT(A_2))(IFWT(A)=merge(IFWT(A_1)−IFFT(A_2),IFWT(A_2))を挙げることができる.
排他演算:直接結論を写す(証明できない)(FWT(A)=(FWT(A_1)+FWT(A_2),FWT(A_1)−FWT(A_2)))(frac{FWT(A_1)+FWT(A_2)}{2},frac{FWT(A_1)−FWT(A_2)}{2}))
同じように、(FWT(A)=(FWT(A_2)−FWT(A_1)、FWT(A_2)+FWT(A_1))=(IFWT(A)=(frac{FWT(A_2)−FWT(A_1)}{2},frac{FWT(A_2)+FWT(A_1)}{2})
テンプレート問題
code:

#include
using namespace std;
typedef long long ll;
const int maxn=(1<<17)+10;
const ll mod=998244353;
const ll inv2=mod+1>>1;
int n,m;
ll A[maxn],B[maxn],a[maxn],b[maxn],c[maxn];
inline ll read()
{
    char c=getchar();ll res=0,f=1;
    while(c'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
    return res*f;
}
void fwt_or(ll* a,int op)
{
    for(int mid=1;mid