問題一覧 > 通常問題

No.1856 Mex Sum 2

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 33
作問者 : 蜜蜂蜜蜂 / テスター : MitarushiMitarushi
1 ProblemId : 6243 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-02-23 20:47:19

問題文

各要素が $0$ 以上 $M$ 以下の長さ $N$ の整数列 $A$ に対し、 $f(A)$ を以下のように定義します。

  • $2^N-1$ 通りありえる $A$ の空でない部分列 $A'$ の全てに対し、 $\mathrm{mex} (A')$ を足し合わした値。( $A$ の部分列とは $A$ の要素を $0$ 個以上いくつか選んで削除し、残ったものを元の順序を保って並べた整数列を表すとします。)
    • なお、整数列 $X$ に対して $\mathrm{mex} (X)$ は $X$ のどの要素とも一致しない $0$ 以上の整数の中で最小のものとします。例えば $\mathrm{mex} \left( \left( 0,1,7 \right) \right) = 2,\mathrm{mex} \left( \left( 2022,77 \right) \right) = 0$ です。

$A$ としてありえる数列は $(M+1)^N$ 通りありますが、その全てに対して $f(A)$ を足し合わせた値を $998244353$ で割った余りを求めてください。

入力

$N\ \ M$

  • $1 \leq N \leq 2000$
  • $1 \leq M \leq 10^9$
  • 入力は全て整数

出力

$(M+1)^N$ 通りある $A$ としてありえる数列全てに対して $f(A)$ を足し合わせた値を $998244353$ で割った余りを出力し、最後に改行してください。

サンプル

サンプル1
入力
2 1
出力
9

$(1+1)^2=4$ 通りありえる $A$ とそれに対応する $f(A)$ の値は以下の通りです。

  • $A=(0,0)$ のとき、 $f(A)=3$ です。
  • $A=(0,1)$ のとき、 $f(A)=3$ です。
  • $A=(1,0)$ のとき、 $f(A)=3$ です。
  • $A=(1,1)$ のとき、 $f(A)=0$ です。
これらの和は $9$ です。

サンプル2
入力
3 2
出力
127

例えば $A=( 0,0,0 )$ のとき、 $f(A)=7$ です。

サンプル3
入力
100 99
出力
275874233

$998244353$ で割った余りを出力してください。

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