問題一覧 > 通常問題

No.1962 Not Divide

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 : PCTprobability / テスター : 👑 tute7627
12 ProblemId : 7830 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-27 21:19:53

問題文

長さ NN の整数列 A1,A2,...,ANA_1,A_2,...,A_N のうち、以下の条件を満たすものの個数  mod 998244353\bmod 998244353 を求めてください。

  • 1≤i≤N1 \le i \le N を満たす ii に対して 1≤Ai≤M1 \le A_i \le M
  • XX のみからなる極大な区間の長さは XX で割り切れない。

入力

N MN\ M

  • 入力は全て整数である。
  • 1≤N≤1091 \le N \le 10^9
  • 1≤M≤1001 \le M \le 100

出力

条件を満たす数列の個数  mod 998244353\bmod 998244353 を出力してください。

サンプル

サンプル1
入力
3 3
出力
5

(A1,A2,A3)=(2,2,2),(2,3,2),(2,3,3),(3,2,3),(3,3,2)(A_1,A_2,A_3) = (2,2,2),(2,3,2),(2,3,3),(3,2,3),(3,3,2) が条件を満たします。

(1,2,2)(1,2,2) は区間 [1,1][1,1] や [2,3][2,3] で条件を満たしません。

(2,2,2)(2,2,2) の区間 [1,2][1,2] は 22 のみから構成され、長さが 22 で割り切れますが極大でないため (2,2,2)(2,2,2) は条件を満たします。

サンプル2
入力
5 7
出力
7017

サンプル3
入力
20225 20
出力
245398672

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