概要

添字andとorの畳み込みの計算方法について勉強したことを書きます。勉強したことと書いてある通り、自分自身が勉強したばかりなので誤り等あるかもしれません。

仕組み

まず畳み込みの定義をします。

数列 $a,b$ が与えられた時に

$\displaystyle c_k = \sum_{ i\ and\ j\ =\ k} a_i * b_j$

$\displaystyle d_k = \sum_{ i\ or\ j\ =\ k} a_i * b_j$

で定義される数列 $c,d$ がそれぞれ、添字andと添字orの畳み込みです。添字に関してandとorで畳み込んでいますね。まずandの畳み込みについて考えます。andの畳み込みができてしまえば、orの畳み込みもほぼ同じ方法でできます。この計算をするために次のような数列の変換 $f$ を考えます。

$\displaystyle f(x)_k = \sum_{i\ or\ k\ =\ i} x_i$

このとき数列の変換 $f$ を行うことによって、

$\displaystyle f(c)_k = f(a)_k * f(b)_k \tag{1}$

となります。つまりもともと畳み込みの計算だったものが各点積という簡単な計算に変化しています。

(1)の証明のようなもの

$\begin{eqnarray} f(a)_k * f(b)_k &=& \sum_{i\ or\ k\ =\ i} a_i * \sum_{j\ or\ k\ =\ j} b_j \\ &=& \sum_{i\ or\ k\ =\ i}\ \sum_{j\ or\ k\ =\ j} a_i * b_j \\ &=& \sum_{s\ or\ k\ =\ s}\ \sum_{i\ and\ j\ =\ s} a_i * b_j \\ &=& \sum_{s\ or\ k\ =\ s} c_s \\ &=& f(c)_k \\ \end{eqnarray}$

2行目から3行目が一番わかりづらいです。 $i\ or\ k\ =\ i,j\ or\ k\ =\ j$ から $i,j$ は $k$ を完全に含んでいるので、 $i\ and\ j\ =\ s$ も $k$ を完全に含んでいるので、えいっとシグマの取り方を変えられます。

fの逆変換

ところでこの計算で求めることができたのは、求めたかった $c$ ではなく $f(c)$ です。もし $f$ の逆変換のようなものがあれば $f(c)$ から $c$ を得ることができます。実はそのような変換は存在します！！

次の変換 $g$ は $f$ の逆変換になっています。

$\displaystyle g(x)_k = \sum_{i\ or\ k\ =\ i} (-1)^{\mathrm{popcount}(i)-\mathrm{popcount}(k)} x_i$

popcount(i)はiの立っているビットの数を表しています。つまりiを立っているビットが表す集合とみたときの集合の要素と等しいです。ちなみに先程の $f$ と異なる部分は-1の累乗をかけている部分だけです。

gとfが互いに逆変換であることの証明のようなもの

$g(f(x)) = x, f(g(x)) = x$ を示せばいいはず。

$\begin{eqnarray} g(f(x))_k &=& \sum_{i\ or\ k\ =\ i} (-1)^{\mathrm{popcount}(i)-\mathrm{popcount}(k)} f(x)_i \\ &=& \sum_{i\ or\ k\ =\ i} (-1)^{\mathrm{popcount}(i)-\mathrm{popcount}(k)} \sum_{j\ or\ i\ =\ j} x_j \\ &=& \sum_{i\ or\ k\ =\ i} \sum_{j\ or\ i\ =\ j} (-1)^{\mathrm{popcount}(i)-\mathrm{popcount}(k)} x_j \\ \end{eqnarray}$

二つのシグマの条件式をみると $k,i,j$ はビットの集合の包含関係として $k \subseteq i \subseteq j$ となっていることがわかります。

[1] $j = k$ のとき

$i = k$ しかないから $x_k$ の係数は $(-1)^{\mathrm{popcount}(k)-\mathrm{popcount}(k)} = 1$ です。

[2] $j \supset k$ のとき

$k \subseteq i \subseteq j$ である $i$ について $(-1)^{\mathrm{popcount}(i)-\mathrm{popcount}(k)}$ の総和をとったものが $x_j$ の係数になります。これは包除原理でよくあるやつで、 $m = \mathrm{popcount}(j)-\mathrm{popcount}(k)$ とすると、

$\begin{eqnarray} \sum_{l=0}^m (-1) ^ l\ _m C_l = \sum_{l=0}^m (1)^{m-l} (-1)^l\ _m C_l = (1-1)^m = 0\ (m > 0) \end{eqnarray}$

が成り立つので $x_j$ の係数は $0$ になります。

よって $g(f(x))_k = x_k$ が成り立つことが示せました。これの逆 $f(g(x))_k = x_k$ も同じ感じで示せます。

添字and畳み込み　

まとめると次の計算をするとandの畳み込みが計算できます。

数列 $a,b$ に変換 $f$ をかける。
それらの数列の各点積を取る。
できた数列に $f$ の逆変換 $g$ をかける。

ちなみにこの $f,g$ には名前がついています。 $f$ をゼータ変換、 $g$ をメビウス変換といいます。ちなみにゼータ変換には上位集合と下位集合のゼータ変換があって、この変換は上位集合のゼータ変換です。メビウス変換も同様でこれは上位集合のメビウス変換です。

下のようなゼータ変換やメビウス変換をよく見ると思うんですが、

$\begin{eqnarray} f(S) = \sum_{T \supseteq S} f(T) \end{eqnarray}$

$\begin{eqnarray} f(S) = \sum_{T \supseteq S} (-1) ^ {|T| - |S|}f(T) \end{eqnarray}$

これは最初に紹介した変換のゼータ変換の添字をビットが表す集合と思うと同じになります。

添字or畳み込み

ここまでandの畳み込みしか書いてきていませんがorの畳み込みも同様にできます。じつは先程の上位集合のゼータ変換、メビウス変換を下位集合ののゼータ変換、メビウス変換に変えるとorの畳み込みになります。下位集合のゼータ変換、メビウス変換は次のような式で表されます。

$\displaystyle f(x)_k = \sum_{i\ or\ k\ =\ k} x_i$

$\displaystyle g(x)_k = \sum_{i\ or\ k\ =\ k} (-1)^{\mathrm{popcount}(k)-\mathrm{popcount}(i)} x_i$

証明もほぼ同じ感じでできると思います。一応集合の形でも書いておきます。

$\begin{eqnarray} f(S) = \sum_{T \subseteq S} f(T) \end{eqnarray}$

$\begin{eqnarray} f(S) = \sum_{T \subseteq S} (-1) ^ {|S| - |T|}f(T) \end{eqnarray}$

高速ゼータ変換、メビウス変換

ゼータ変換やメビウス変換を愚直にやると数列の長さをNとして $\mathcal{O} (N ^ 2)$ かかります。これを $\mathcal{O}(Nlog(N))$ で行うのが高速ゼータ変換、メビウス変換です。高速ゼータ変換、メビウス変換ができればandとorの畳み込みは $\mathcal{O}(Nlog(N))$ で計算することができます。説明は省略しますが、下のようなコードで実現できます。bitdpのようなことをやっているらしい。それぞれのbitについて累積和をしているといってもいいかも。配列の長さは2の冪乗にしておくといいと思います。

コード

間違っている可能性があります。

上位集合のゼータ変換

void zeta_sup(vector<int> &f) {
    int n = (int)f.size();
    for (int i = 1;i < n;i <<= 1) {
        for (int j = 0;j < n; j++) {
            if (!(j&i)) f[j] += f[j|i];
        }
    }
}

上位集合のメビウス変換

void mebius_sup(vector<int> &f) {
    int n = (int)f.size();
    for (int i = 1;i < n;i <<= 1) {
        for (int j = 0;j < n; j++) {
            if (!(j&i)) f[j] -= f[j|i];
        }
    }
}

下位集合のゼータ変換

void zeta_sub(vector<int> &f) {
    int n = (int)f.size();
    for (int i = 1;i < n;i <<= 1) {
        for (int j = 0;j < n; j++) {
            if (j&i) f[j] += f[j^i];
        }
    }
}

下位集合のメビウス変換

void mebius_sub(vector<int> &f) {
    int n = (int)f.size();
    for (int i = 1;i < n;i <<= 1) {
        for (int j = 0;j < n; j++) {
            if (j&i) f[j] -= f[j^i];
        }
    }
}

andの畳み込み

vector<int> and_convolution(vector<int> a,vector<int> b) {
    assert(a.size() == b.size());
    zeta_sup(a);
    zeta_sup(b);
    int n = (int)a.size();
    for(int i = 0;i < n; i++) a[i] *= b[i];
    mebius_sup(a);
    return a;
}

orの畳み込み

vector<int> or_convolution(vector<int> a,vector<int> b) {
    assert(a.size() == b.size());
    zeta_sub(a);
    zeta_sub(b);
    int n = (int)a.size();
    for(int i = 0;i < n; i++) a[i] *= b[i];
    mebius_sub(a);
    return a;
}

参考

https://misteer.hatenablog.com/entry/zeta-moebius

https://kazuma8128.hatenablog.com/entry/2018/05/31/144519

kapibara’s diary

添字and,or畳み込み

概要

仕組み