No.931 Multiplicative Convolution

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 29
作問者 : risujirohrisujiroh / テスター : pockynypockyny
6 ProblemId : 3473 / 出題時の順位表
問題文最終更新日: 2019-11-22 19:03:57

問題文

素数$P$と整数列$A_1,A_2,\dots,A_{P-1}$,$B_1,B_2,\dots,B_{P-1}$が与えられます.
整数列$C_1,C_2,\dots,C_{P-1}$を求めてください.
ただし,
\[
C_k=\sum_{1 \le i,j \lt P\\ k=(i\times j) \mod P}A_iB_j
\]
とし,これを$998244353$で割った余りを出力してください.
(つまり,$C_k$は$i\times j$を$P$で割った余りが$k$となるような全ての組$(i,j)$について$A_iB_j$を足し合わせたものです.)

制約

・$2\le P\le 99991$
・$0\le A_i,B_i \lt 998244353$
・入力はすべて整数
・$P$は素数

入力

$P$
$A_1\ A_2\ \dots\ A_{P-1}$
$B_1\ B_2\ \dots\ B_{P-1}$

出力

$C_1,C_2,\dots,C_{P-1}$を$998244353$で割った余りを空白区切りで出力してください.
最後に改行してください。

サンプル

サンプル1
入力
3
1 2
3 4
出力
11 10

$C_1=A_1B_1+A_2B_2\mod 998244353=11$
$C_2=A_1B_2+A_2B_1\mod 998244353=10$
となります.

サンプル2
入力
11
2 3 5 8 1 3 2 1 3 4
5 5 8 9 1 4 4 2 3 3
出力
172 129 138 127 162 138 149 148 129 116

サンプル3
入力
2
8886
112339
出力
1

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。