問題一覧 > 通常問題

No.2487 Multiple of M

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 24
作問者 : ytqm3 / テスター : Cyanmond
お気に入りにしたユーザー ProblemId : 10195 / 自分の提出
問題文最終更新日: 2023-09-30 11:46:55
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 406 技術室奥プログラミングコンテスト#7 Day2 (順位表) の他の問題:

Problem Statement

Find the number, modulo $998244353$, of integer sequences $A=(A_0,A_1,\ldots,A_{N-1})$ of length $N$ that satisfy the following conditions.

  • $1 \le A_i \le M-1\ (0 \le i < N)$
  • $\displaystyle \sum_{i=0}^{N-1} A_iK^i$ is a multiple of $M$

(Original idea: highlighter)

Input

$N$ $M$ $K$
  • $1 \le N,K \le 10^9$
  • $2 \le M \le 998244352$ (corrected 9/30 11:46)
  • All input values are integers

Output

Output the answer.

Sample

Sample 1
Input
3 4 1
Output
6

For example, $A=(1,2,1)$ satisfies the conditions.

Sample 2
Input
1 2 1
Output
0
Sample 3
Input
314 159 265
Output
924650454

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。