No.1962 Not Divide
タグ : / 解いたユーザー数 25
作問者 :
PCTprobability
/ テスター :
👑
tute7627
Problem Statement
Find the number, modulo $\bmod 998244353$, of integer sequences $A_1,A_2,...,A_N$ of length $N$ that satisfy the following conditions.
- For each $i$ satisfying $1 \le i \le N$, $1 \le A_i \le M$.
- The length of every maximal segment consisting only of $X$ is not divisible by $X$.
Input
$N\ M$
- All inputs are integers.
- $1 \le N \le 10^9$
- $1 \le M \le 100$
Output
Output the number, $\bmod 998244353$, of sequences that satisfy the conditions.
Sample
Sample 1
Input
3 3
Output
5
$(A_1,A_2,A_3) = (2,2,2),(2,3,2),(2,3,3),(3,2,3),(3,3,2)$ satisfy the conditions.
$(1,2,2)$ does not satisfy the conditions because of the segments $[1,1]$ and $[2,3]$.
In $(2,2,2)$, the segment $[1,2]$ consists only of $2$ and its length is divisible by $2$, but it is not maximal, so $(2,2,2)$ satisfies the conditions.
Sample 2
Input
5 7
Output
7017
Sample 3
Input
20225 20
Output
245398672
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。