問題一覧 > 通常問題

No.2936 Sum of Square of Mex

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 : nouka28 / テスター : tnodino hirayuu_yc mymelochan kusirakusira Nyaa Uruzu
2 ProblemId : 11475 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-10-12 10:54:27

問題文

正整数 NN と非負整数 MM が与えられます。

0≤Ai≤M0\leq A_i\leq M を満たす長さ NN の非負整数列 AA は (M+1)N(M+1)^N 通りありますが、

それらすべてに対する mex(A)2\mathrm{mex}(A)^2 の総和を 998244353998244353 で割ったあまりを求めてください。

制約

  • 1≤N≤2×1051\leq N\leq 2\times 10^5
  • 0≤M≤1090\leq M\leq 10^9

入力

NN MM

入力は以下の形式で標準入力から与えられる。

出力

答えを出力せよ。

サンプル

サンプル1
入力
2 2
出力
11
  • A=(0,0)A=(0,0) のとき、mex(A)2=12=1\mathrm{mex}(A)^2=1^2=1 です。
  • A=(0,1)A=(0,1) のとき、mex(A)2=22=4\mathrm{mex}(A)^2=2^2=4 です。
  • A=(0,2)A=(0,2) のとき、mex(A)2=12=1\mathrm{mex}(A)^2=1^2=1 です。
  • A=(1,0)A=(1,0) のとき、mex(A)2=22=4\mathrm{mex}(A)^2=2^2=4 です。
  • A=(1,1)A=(1,1) のとき、mex(A)2=02=0\mathrm{mex}(A)^2=0^2=0 です。
  • A=(1,2)A=(1,2) のとき、mex(A)2=02=0\mathrm{mex}(A)^2=0^2=0 です。
  • A=(2,0)A=(2,0) のとき、mex(A)2=12=1\mathrm{mex}(A)^2=1^2=1 です。
  • A=(2,1)A=(2,1) のとき、mex(A)2=02=0\mathrm{mex}(A)^2=0^2=0 です。
  • A=(2,2)A=(2,2) のとき、mex(A)2=02=0\mathrm{mex}(A)^2=0^2=0 です。

したがって答えは 1+4+1+4+0+0+1+0+0=111+4+1+4+0+0+1+0+0=11 となります。

サンプル2
入力
1 0
出力
1
サンプル3
入力
31415 926535897
出力
170588663

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