[問題案] Convolution on the multiplicative monoid of Z/NZ

[maspypy]

問題名: Convolution on the multiplicative monoid of Z/NZ

問題概要

整数列 a_0, a_1, ..., a_{N-1}, b_0, ..., b_{N-1} が与えられる。c_0, ..., c_{N-1} を求めよ。 c_k = \sum_{ij=k mod N}a_ib_j

入力

N\leq 2^{18} くらい。

参考資料

https://twitter.com/tatyam_prime/status/1478706478144167936?s=20 以下の一連のツイート https://github.com/yosupo06/library-checker-problems/issues/746

想定アルゴリズム

$N = 2^n$ の場合と同じようにする。

d = gcd(N, i) によって元を分類し、d ごとに群 (Z/(N/d))^x での FFT を行う。 d1 = gcd(N, i), d2 = gcd(N, j) として、d1, d2 の寄与を適当に足しこむ。 足しこむ先は、元の群の~~部分群~~剰余群になっている。大きい群の FFT の一部分を読めば小さい群の FFT になっていることから、一度だけ FFT をしておいて適当な積を足していくだけでよい。

計算量

全ての約数 d をわたって、群 (Z/dZ)^x の FFT を行う必要があるが、 https://github.com/yosupo06/library-checker-problems/issues/746 によれば、これは個々の d に対して O(phi(d) log phi(d)) 時間である（phi：euler）。 sum_d phi(d) = N に注意すれば、全部個別に FFT しても計算量が O(NlogN) であることが分かる。

すべての d1, d2 に対して d3 個の各点積をとる必要があるが、これも O(NlogN) である。（要確認）

---

忘れないうちに書き込んだが、

https://github.com/yosupo06/library-checker-problems/issues/746

の解決が前提である。