No.2487 Multiple of M
問題文最終更新日: 2023-09-30 11:46:55
English (AI translation)
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
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もしくは右上の雲マークをクリックしてアカウントを作成してください。