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 で与えられた数列を直に返していますが、説明のため a に fwt を適用した数列を cb に fwt を適用した数列を d と置きます。

fwt をした際に、 c_j に対する a_i の係数を考えます。 a_j=x+y,a_{i\ \mathrm{xor}\ j}=x-y の部分について、マイナスがかかっているのは a_{i\ \mathrm{xor}\ j}=x-y-y のみです。各 bit に対し 1 回ずつ for 文が回ってくることを考えると、-1 がかかる回数は ij\mathrm{bitand} の立っている bit 数に等しいことがわかります。 よって、c_j に対する a_i の寄与は (-1)^{\mathrm{popcount}(i\ \mathrm{and}\ j)} となります。 より、\displaystyle c_j = \sum_{i=0}^{n-1} a_i \times (-1)^{\mathrm{popcount}(i\ \mathrm{and}\ j)} です。

ここで、cd の各点積を取った数列 x を求めます。また、x に fwt を適用した数列を y とします。a_i \times b_jx_k,y_k に対する寄与を求めます。 x_k に対する寄与は (-1)^{\mathrm{popcount}(i\ \mathrm{and}\ k)} \times (-1)^{\mathrm{popcount}(j\ \mathrm{and}\ k)} = (-1)^{\mathrm{popcount}((i\ \mathrm{xor}\ j)\ \mathrm{and}\ k)} です。

y_{h} に対する寄与は、

 \begin{align}
y_h &= \displaystyle \sum_{k=0}^{n-1} x_k \times (-1)^{\mathrm{popcount}(h\ \mathrm{and}\ k)} \\
&= \displaystyle \sum_{k=0}^{n-1}  (-1)^{\mathrm{popcount}((i\ \mathrm{xor}\  j)\ \mathrm{and}\ k)} \times (-1)^{\mathrm{popcount}(h\ \mathrm{and}\ k)} \\
&= \displaystyle \sum_{k=0}^{n-1}  (-1)^{\mathrm{popcount}((i\ \mathrm{xor}\  j\ \mathrm{xor}\ h)\ \mathrm{and}\ k)}
\end{align}

となり、i\ \mathrm{xor}\ j = h の時は (i\ \mathrm{xor}\  j\ \mathrm{xor}\ h)=0 となり寄与の係数は n、そうでない時は (i\ \mathrm{xor}\  j\ \mathrm{xor}\ h) の最小の bit を取ることで対称性により寄与の係数が 0 であることを示せます。

より、最後に y の全ての項を n で割ることにより ab の xor 畳み込みを得ることが出来ました。計算量は \mathrm{O}(N\log N) です。

使用例 judge.yosupo.jp