問題一覧 > 通常問題

No.2936 Sum of Square of Mex

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

問題文

正整数 $N$ と非負整数 $M$ が与えられます。

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

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

制約

  • $1\leq N\leq 2\times 10^5$
  • $0\leq M\leq 10^9$

入力

$N$ $M$

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

出力

答えを出力せよ。

サンプル

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

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

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

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