No.2487 Multiple of M
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 :
ytqm3
/ テスター :
Cyanmond
タグ : / 解いたユーザー数 24
作問者 :
ytqm3
/ テスター :
Cyanmond
問題文最終更新日: 2023-09-30 11:46:55
問題文
長さ $N$ の整数列 $A=(A_0,A_1,\ldots,A_{N-1})$ であって、以下の条件を満たすものの個数を $998244353$ で割った余りを求めてください。
- $1 \le A_i \le M-1\ (0 \le i < N)$
- $\displaystyle \sum_{i=0}^{N-1} A_iK^i$ は $M$ の倍数
(原案 : highlighter)
入力
$N$ $M$ $K$
- $1 \le N,K \le 10^9$
- $2 \le M \le 998244352$ (9/30 11:46 修正)
- 入力はすべて整数
出力
答えを出力せよ。
サンプル
サンプル1
入力
3 4 1
出力
6
例えば、 $A=(1,2,1)$ のとき条件を満たします。
サンプル2
入力
1 2 1
出力
0
サンプル3
入力
314 159 265
出力
924650454
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。