問題一覧 > 通常問題

No.2951 Similar to Mex

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 18
作問者 : nouka28nouka28 / テスター : aplysiaSheepaplysiaSheep とりゐとりゐ t9unkubjt9unkubj
1 ProblemId : 10797 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-10-25 21:21:24

問題文

整数列 $A=(A_1,A_2,\dots,A_{|A|})$ と整数 $k$ について $f(A,k)$ を以下のように定義します。

  • $f(A,k) =$ ( $A$ に含まれない $k$ 以上の最小の整数 )

正整数 $N,M,K$ が与えられます。

各要素が $1$ 以上 $M$ 以下の整数である長さ $N$ の数列 $A$ は $M^N$ 通り考えられますが、

その全てに対する $\displaystyle \prod_{k=1}^{K}f(A,k)$ の総和を $998244353$ で割ったあまりで答えてください。

制約

  • $1\leq N,M,K\leq 300$
  • 入力はすべて整数

入力

$N$ $M$ $K$

出力

答えを出力せよ。

サンプル

サンプル1
入力
2 3 2
出力
43

条件を満たす $A$ は以下の $9$ 通りあります。

  • $A=(1,1)$ のとき、 $f(A,1)\cdot f(A,2)=2\cdot 2=4$
  • $A=(1,2)$ のとき、 $f(A,1)\cdot f(A,2)=3\cdot 3=9$
  • $A=(1,3)$ のとき、 $f(A,1)\cdot f(A,2)=2\cdot 2=4$
  • $A=(2,1)$ のとき、 $f(A,1)\cdot f(A,2)=3\cdot 3=9$
  • $A=(2,2)$ のとき、 $f(A,1)\cdot f(A,2)=1\cdot 3=3$
  • $A=(2,3)$ のとき、 $f(A,1)\cdot f(A,2)=1\cdot 4=4$
  • $A=(3,1)$ のとき、 $f(A,1)\cdot f(A,2)=2\cdot 2=4$
  • $A=(3,2)$ のとき、 $f(A,1)\cdot f(A,2)=1\cdot 4=4$
  • $A=(3,3)$ のとき、 $f(A,1)\cdot f(A,2)=1\cdot 2=2$

したがって、答えは $4+9+4+9+3+4+4+4+2=43$ となります。

サンプル2
入力
1 1 1
出力
2
  • $A=(1,1)$ のとき、 $f(A,1)=2$

したがって、答えは $2$ となります。

サンプル3
入力
40 40 40
出力
801530328

$998244353$ で割ったあまりを求めてください。

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