[問題案] Multivariate Cyclic Convolution
maspypy opened this issue · 6 comments
問題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 の FT が高速に計算できることを利用する。
https://dic.kimiyuki.net/chirp-z-transform
高次元の FFT → 各点積 → IFFT
想定計算量
O(NlogN)
制約・入力・出力
https://judge.yosupo.jp/problem/multivariate_convolution に準ずる。
完全に同じ制約、全く同じ入力ケースにしてサボることを提案する。
結局 mod 998244353 はやめた
参考資料
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) みたいな表記の方が並びが分かりやすいかも。
理解しました ありがとうございます 良さそうに思えます
- 定数倍がすごそう？
- 誤差: もちろん理想的には2か3がいいのですが、「TODO: いつか2か3の解法と差し替える」で1でもいいと思います
ありがとうございます。実装難しそうなのでちょっと時間かかりますが、やってみます。
実用上は mod p の場合の出題しか見たことがなくて、mod p だと実装量がだいぶ変わりますが、これもついでに作りますか？わざわざ用意するほどではないですかね。
あ、mod p と書いたのは、「convolution on mul monoid」との混同です。
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.)
やっぱり p = 998244353 ではなく、p=1 mod n_i にしようと思います。そろそろ作業します。