[問題案] Convolution on the Multiplicative Monoid of Z/pZ

[maspypy]

[問題概要] https://judge.yosupo.jp/problem/mul_mod2n_convolution を mod p（p は素数）にしたもの

[制約] $p\leq 2^{19}$

[解法] $i,j\neq 0$ 部分の処理を考える。原始根をとると長さ $p-1$ の巡回畳み込みに帰着。

まあまあよく出るし見た目的にも LC に作っておこうかなという。 ところで最近また、一般 mod n で実装しておくこと興味があるが、 いずれにせよ素数に限定したものと比べてだいぶ実装量が多いかつ出題がないのでやるにしても別問題。

[Misuki743]

Hello, I'd like to help preparing the problem, though I'm not very familiar about the preparation, it may take some time.

[maspypy]

Thank you! Feel free to ask if you have any troubles.

[Misuki743]

About the constraint of the sequence, do we need to force $a_0 = b_0 = 0$? I think it is more clean to force it, while the normal constraint $(0 \le a_0, b_0 < 998244353)$ would be better for general purpose.

[maspypy]

I was intended that, $a_0, b_0$ can be non-zero. （same as https://judge.yosupo.jp/problem/mul_mod2n_convolution ）

In some competitive programming problems (ex https://atcoder.jp/contests/agc047/tasks/agc047_c ), we need to handle $a_0$ and $b_0$ correctly. Therefore, I believe it would be beneficial if we could also verify the operation.

[Misuki743]

ok, I've finished writing the statement, is there any problem about the statement?

English statement

Given a prime $P$ and integer sequences $a_0, a1, ..., a{P - 1}$ and $b_0, b1, ..., b{P - 1}$. Calculate an integer sequence $c_0, c1, ..., c{P - 1}$ as follows:

$$ck = \sum{i \times j \equiv k \pmod{P}} a_i b_j \bmod 998244353$$

• $2 \leq P \leq 2^{19}$
• $P$ is a prime
• $0 \leq a_i, b_i < 998244353$

Japanese statement

素数 $P$ と整数列 $a_0, a1, ..., a{P - 1}$ 、 $b_0, b1, ..., b{P - 1}$ が与えられます。整数列 $c_0, c1, ..., c{P - 1}$ を求めてください。

ただし、

$$ck = \sum{i \times j \equiv k \pmod{P}} a_i b_j \bmod 998244353$$

です

• $2 \leq P \leq 2^{19}$
• $P$ は素数
• $0 \leq a_i, b_i < 998244353$

[maspypy]

It's ok!

[Misuki743]

1100