これを として時間計算量 で解きます。
畳み込み
ゼータ変換・メビウス変換を理解する - Qiita
添え字 gcd での畳み込みで AGC038-C を解く - noshi91のメモ
添え字の での畳み込みをおおまかに理解しているとします。
は行列 を用いて と表現できます。
これを軸にして式変形を行います。
値の定義と記法
添え字は 1-indexed
アイバーソンの記法 - Wikipedia
- 行列
- 単位ベクトル
- 入力 を表すベクトル
- ベクトル同士の各点積
演算子の優先度は行列積より低いとする
例えば、 畳み込みは
となる。
また、 行列と 次元ベクトルの同一視などを断りなく行う。
アルゴリズム
についての答えは以下のように書くことが出来る。
と を で畳み込みすれば、その第 成分は なる の個数となる。
これを式変形すると
よって に依存しない部分を新しく文字で置いて
とすれば、求める値は
となることが分かった。
すなわち の各成分を出力すればよい。
及びその転置や逆行列とベクトルとの積を で計算するアルゴリズムを用いれば、この問題を解くことが出来る。
実装例
Submission #9522125 - 「みんなのプロコン 2018」決勝
分かりやすさのため の実装になっています。