No.931 Multiplicative Convolution
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 66
作問者 :
risujiroh
/ テスター :
pockyny
タグ : / 解いたユーザー数 66
作問者 :
risujiroh
/ テスター :
pockyny
問題文最終更新日: 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
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。