xor 畳み込みの線形代数を使わない説明
xor 畳み込みについて、線形代数を使わない日本語資料が見つからなかったため xor 畳み込みの線形代数を使わない理解について解説します。
template<class T> void fwt(vector<T> &a){ ll n=a.size(); for(int i=1;i<n;i*=2){ for(int j=0;j<n;j++){ if((j&i)==0){ T x=a[j],y=a[i^j]; a[j]=x+y; a[i^j]=x-y; } } } } template<class T> vector<T> xorconv(vector<T> a,vector<T> b){ fwt(a); fwt(b); for(int i=0;i<b.size();i++) a[i]*=b[i]; fwt(a); T inv=T(1)/T(a.size()); //T が int などの場合は切り捨てとなってしまうため注意 for(int i=0;i<a.size();i++) a[i]*=inv; return a; }
実装では fwt で与えられた数列を直に返していますが、説明のため に fwt を適用した数列を 、 に fwt を適用した数列を と置きます。
fwt をした際に、 に対する の係数を考えます。 の部分について、マイナスがかかっているのは の のみです。各 bit に対し 回ずつ for 文が回ってくることを考えると、 がかかる回数は と の の立っている bit 数に等しいことがわかります。 よって、 に対する の寄与は となります。 より、 です。
ここで、 と の各点積を取った数列 を求めます。また、 に fwt を適用した数列を とします。 の , に対する寄与を求めます。 に対する寄与は です。
に対する寄与は、
となり、 の時は となり寄与の係数は 、そうでない時は の最小の bit を取ることで対称性により寄与の係数が であることを示せます。
より、最後に の全ての項を で割ることにより と の xor 畳み込みを得ることが出来ました。計算量は です。
使用例 judge.yosupo.jp