色々な畳み込み
最近覚えたのでメモ.
理論とか仕組みとかの説明はしません.
高速フーリエ変換(FFT)
高速ゼータ変換(FZT)
上位/下位集合の畳み込み
- Σ(j ⊂ i) a_i = b_j
または
- Σ(i ⊂ j) a_i = b_j
この形で長さ n の列 a から長さ n の列 b を求めます. ただし n は2の冪乗とします.
やってることは実質 bitDP みたいな感じ.
計算量は O(nlogn) です.
コード
template <typename T> void fzt(vector<T>& f) { int n = f.size(); for (int i = 1; i < n; i <<= 1) { for (int j = 0; j < n; j++) { if ((j & i) == 0) { f[j] += f[j | i]; // この場合上位集合の畳み込みになる // 左辺と右辺を逆にすると下位集合の畳み込みになる } } } }
高速メビウス変換(FMT)
ゼータ変換の逆変換
- Σ(j ⊂ i) (-1)^|i \ j| * a_i = b_j
または
- Σ(i ⊂ j) (-1)^|j \ i| * a_i = b_j
この形で長さ n の列 a から長さ n の列 b を求めます. ただし n は2の冪乗とします.
計算量は O(nlogn) です.
コード
template <typename T> void fmt(vector<T>& f) { int n = f.size(); for (int i = 1; i < n; i <<= 1) { for (int j = 0; j < n; j++) { if ((j & i) == 0) { f[j] -= f[j | i]; // この場合上位集合のゼータ変換の逆変換になる // 左辺と右辺を逆にすると下位集合のゼータ変換の逆変換になる } } } }
高速アダマール変換(FWT)
添え字ANDでの畳み込み
- Σ(i & j = k) a_i * b_j = c_k
この形で長さ n の列 a, b から長さ n の列 c を求めます. ただし n は2の冪乗とします.
列 a, b を離散アダマール変換をして, かけ合わせてから逆変換すると c が求まります.
上位集合での高速ゼータ変換+高速メビウス変換と同じです.
計算量は O(nlogn) です.
コード
template <typename T> void fwt(vector<T>& f) { int n = f.size(); for (int i = 1; i < n; i <<= 1) { for (int j = 0; j < n; j++) { if ((j & i) == 0) { f[j] += f[j | i]; } } } } template <typename T> void ifwt(vector<T>& f) { int n = f.size(); for (int i = 1; i < n; i <<= 1) { for (int j = 0; j < n; j++) { if ((j & i) == 0) { f[j] -= f[j | i]; } } } }
添え字ORでの畳み込み
- Σ(i | j = k) a_i * b_j = c_k
この形で長さ n の列 a, b から長さ n の列 c を求めます. ただし n は2の冪乗とします.
ANDとほぼ同じですが, 足される方向が逆になってます.
下位集合での高速ゼータ変換+高速メビウス変換と同じです.
計算量は O(nlogn) です.
コード
template <typename T> void fwt(vector<T>& f) { int n = f.size(); for (int i = 1; i < n; i <<= 1) { for (int j = 0; j < n; j++) { if ((j & i) == 0) { f[j | i] += f[j]; } } } } template <typename T> void ifwt(vector<T>& f) { int n = f.size(); for (int i = 1; i < n; i <<= 1) { for (int j = 0; j < n; j++) { if ((j & i) == 0) { f[j | i] -= f[j]; } } } }
添え字XORでの畳み込み
- Σ(i ^ j = k) a_i * b_j = c_k
この形で長さ n の列 a, b から長さ n の列 c を求めます. ただし n は2の冪乗とします.
列 a, b を離散アダマール変換をして, かけ合わせてから逆変換すると c が求まります.
ifwt は2で除算する必要があるので注意.
ちなみに, 逆変換は fwt してから全要素を n で割ることでもできます.
計算量は O(nlogn) です.
コード
template <typename T> void fwt(vector<T>& f) { int n = f.size(); for (int i = 1; i < n; i <<= 1) { for (int j = 0; j < n; j++) { if ((j & i) == 0) { T x = f[j], y = f[j | i]; f[j] = x + y, f[j | i] = x - y; } } } } template <typename T> void ifwt(vector<T>& f) { int n = f.size(); for (int i = 1; i < n; i <<= 1) { for (int j = 0; j < n; j++) { if ((j & i) == 0) { T x = f[j], y = f[j | i]; f[j] = (x + y) / 2, f[j | i] = (x - y) / 2; } } } }
その他
参考URL
http://d.hatena.ne.jp/nurs/20130617/1371483633 : FFT
http://omochan.hatenablog.com/entry/2017/09/26/235331 : FZT/FMT
https://pekempey.hatenablog.com/entry/2016/10/30/205852 : FZT/FMT
http://apps.topcoder.com/wiki/display/tc/SRM+518 : FWT
https://blog.csdn.net/xuanandting/article/details/70991372 : FWT
