Convolution 練習問題まとめ

NTT (高速数論変換)を利用した Convolution の各種テクニックが学べる問題をリストにしました。Karatsuba乗算についても少し触れています。

  1. F - Convolution 
    まずはNTTライブラリの確認から。

  2. A - コンテスト
    簡単な問題です。NTTだと mod をとってしまうため畳み込み後の値が 0 なのか 998244353 の倍数なのかが判定できませんが、この問題では撃墜するようなケースは入っていません。心配なら複数の NTT-friendly な mod で計算して全て 0 になることを確かめると良いと思います。

  3. 065 - RGB Balls 2（★7）
    一手考察が必要ですが、基本的な問題です。
    ヒント：それぞれの条件を言い換えます。二色についての条件になっているのが厄介なので、K を使って一色ごとの条件に言い換えましょう。

  4. No.1195 数え上げを愛したい（文字列編） - yukicoder
    素朴なDPをNTTを使って高速化します。
    ヒント：遷移の係数を、i のみに依存する項、j のみに依存する項、i + j のみに依存する項の積の3つに分解できると畳み込みができます。

  5. https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3281
    木DPでは部分木のDPテーブルをマージする操作が畳み込みの形になっていることがよくあります。
    おまけ：No.196 典型DP (1) - yukicoder　これと比較してみると面白いかもしれません。こちらはNTTが要りません(”二乗の木DP")。木DPの畳み込みだと二乗の木DPの方がメジャーですかね？

  6. No.206 数の積集合を求めるクエリ - yukicoder
    少し工夫すれば畳み込みで解くことができます。
    ヒント：各 v について、 i = j + v となるような (i,j) について A[i]*B[j] の和が取れれば良いです。これは i - j = v について畳み込みをすれば良いです。

  7. F - Substring 2
    少し難しいですが、畳み込みで解けるとわかった上で考察を進めれば多少楽になります。下のパターンマッチングの記事も参考になります。
    ヒント：({0,1}, xor) は ({1,-1}, *) と置き換えることができます。

  8. C - Product Modulo
    有名問題です。少し知識が必要です。積に関する畳み込みをうまく和に関する畳み込みに帰着します。
    必要な知識：原始根。一応NTT内部でも原始根は使われていますね。ヒストグラムにしてから畳み込むというのも少し面白いです。

  9. Multiset's Subset's Product Sum Hard | MojaCoder
    多数の小さな配列を畳み込む必要があります。
    必要な知識：いわゆるマージテク。マージテクにはいくつかの種類があります。 マージテクと高さ O(logn) のマージ過程との融合 | Mathenachia　

  10. https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2959
    少し考察が必要ですが、中央を固定すると畳み込みの形で書くことができます。畳み込みに i < j の制約がついていますが、頑張るとNTTで畳み込むことができます。
    ヒント： j - i = k - j で j について畳み込めば良いですが、これは i + k = j * 2 ( i < k )とすれば良いです。不等式の制約は分割統治で解消できます。配列を前後2つに区切ることでより小さい問題に帰着しましょう。ちなみにKaratsuba法だと計算量が悪化しません。

  11. 工事中
    ヒント：online-convolution, relaxed-convolution とか呼ばれるタイプの畳み込みです。9, 10, 11 はどれも分割統治NTTと呼ばれることがあるので、少し混乱を招きそうですね。online の問題を offline の問題に帰着して解く問題だと、他には Monotone-Minima を使うものが有名でしょうか(この手の問題を募集しています)。

 

興味深い資料

その他

  • long long での畳み込み
    長さN、各要素が long long に収まる配列A, Bを畳み込んで配列Cを得るとします。 こういった時に mod 998244353 を取った値ではなく本来の値が欲しくなる時があります。これは簡単で、複数の mod を用いて NTT を使った畳み込みをした後、中国剰余定理で復元すれば良いです。C の各要素の大きさが 1e18 以下であることが保証されているならば、NTT-friendly な mod の組として (998244353, 1224736769) の組が使えます。この2つの積は 1.2e18 程度で、1e18 を超えるため中国剰余定理で復元できます。long long は最大で 9.2e18 程度になるので、そこまで見るなら3つの組にする必要があります。ACLだと (754974721, 167772161, 469762049) を使っています。この積は 6e25 程度なので余裕ですね。

  • 任意modでの畳み込み
    例えば mod 1e9+7 などで畳み込みをしたい時があるかもしれません。とりたい mod を M とします。A,B (mod M) から C (mod M)を得ることにします。これもlong long の時のように A,B (mod M) から C (mod をとる前) を得て、C の各要素を mod M で置き換えれば良いです。*1求めたい mod が 2^32 以内かつ配列の長さが 1e6 程度なら C (mod をとる前) の最大値は 1e25 程度なので、 先ほどの(754974721, 167772161, 469762049) が使えます。mod をとる前の C の最大値は long long には入らない場合があることに注意してください。 int128 を使ったり、garnerのアルゴリズムを使うことでオーバーフローを回避できます。

*1:正当性: 畳み込みを定義通り計算すると和と積を取るだけなので一時的に mod を外して後でとり直しても大丈夫。