[問題案] Multivariate Cyclic Convolution

[maspypy]

問題ID: multivariate_cyclic_convolution 問題名: Multivariate Cyclic Convolution

問題概要

k変数の多項式 f(x_1, x_2, ..., x_k), g(x_1, x_2, ..., x_k) が与えられる。これを掛けて mod (x_1^{n_1}-1, x_2^{n_2}-1, ..., x_k^{n_k}-1) を取ったものを求めてください。

想定アルゴリズム

1 の 2^n 乗根と m 乗根がある体において、Z/mZ の FFT が高速に計算できることを利用する。 https://dic.kimiyuki.net/chirp-z-transform 高次元の FFT → 各点積 → IFFT

（方針 1）複素数体 C を使う。上位ビットと下位ビットに分けるなどして計算誤差をおさえて正しい解を得る。 （方針 2）p = 1 mod (2^nN) となる素数をとって、mod p で計算 → garner でマージ。 （方針 3）中国剰余定理で巡回群の個数を減らすなどして、いくつかの軸は長さ 2^n の巡回群に埋め込めば、欲しい m 乗根を全部含む p を、32 bit 以内でとる。

（実装がつらそうなので 方針1 をとりたいが、誤差評価とか、最悪ケースのテストケース作りに自信がないやつ）

想定計算量

O(NlogN)

制約・入力・出力

https://judge.yosupo.jp/problem/multivariate_convolution に準ずる。 完全に同じ制約、全く同じ入力ケースにしてサボることを提案する。

• 想定計算量オーダーが K 倍違う
• 998244353 出題でありながら、現時点で挙げられている方針では 998244353 が活きない

ことを remark しておきますが、これでいいんじゃないかと思っています。

参考資料

https://dic.kimiyuki.net/chirp-z-transform https://twitter.com/noshi91/status/1478716471136366593?s=20 以下のツイートの議論

問題名

https://en.wikipedia.org/wiki/Circular_convolution

Circular convolution, also known as cyclic convolution, is a ...

なので、cyclic か circular のどちらか。 Multivariate Convolution (Cyclic) みたいな表記の方が並びが分かりやすいかも。

[yosupo06]

理解しました　ありがとうございます　良さそうに思えます

• 定数倍がすごそう？
• 誤差: もちろん理想的には2か3がいいのですが、「TODO: いつか2か3の解法と差し替える」で1でもいいと思います

[maspypy]

ありがとうございます。実装難しそうなのでちょっと時間かかりますが、やってみます。

実用上は mod p の場合の出題しか見たことがなくて、mod p だと実装量がだいぶ変わりますが、これもついでに作りますか？わざわざ用意するほどではないですかね。

[maspypy]

あ、mod p と書いたのは、「convolution on mul monoid」との混同です。

[hly1204]

One may want to check the paper Notes on the Truncated Fourier Transform. I hope it would be helpful. (Though I haven't understand yet.)

[maspypy]

やっぱり p = 998244353 ではなく、p=1 mod n_i にしようと思います。そろそろ作業します。

[maspypy]

done https://github.com/yosupo06/library-checker-problems/pull/902