問題一覧 > 通常問題

No.2951 Similar to Mex

レベル : / AI推定難易度 : 1950 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 24
作問者 : nouka28 / テスター : aplysiaSheep とりゐ t9unkubj
お気に入りにしたユーザー ProblemId : 10797 / 自分の提出
問題文最終更新日: 2024-10-25 21:21:24
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 451 (並木中等プログラミングコンテスト 2024) (順位表) の他の問題:

Problem Statement

For an integer sequence $A=(A_1,A_2,\dots,A_{|A|})$ and an integer $k$, define $f(A,k)$ as follows.

  • $f(A,k) =$ ( the smallest integer that is at least $k$ and is not contained in $A$ )

You are given positive integers $N,M,K$.

There are $M^N$ possible sequences $A$ of length $N$ whose elements are all integers between $1$ and $M$, inclusive.

Find the sum of $\displaystyle \prod_{k=1}^{K}f(A,k)$ over all of them, modulo $998244353$.

Constraints

  • $1\leq N,M,K\leq 300$
  • All input values are integers.

Input

$N$ $M$ $K$

Output

Output the answer.

Sample

Sample 1
Input
2 3 2
Output
43

There are $9$ sequences $A$ satisfying the conditions, as follows.

  • When $A=(1,1)$, $f(A,1)\cdot f(A,2)=2\cdot 2=4$
  • When $A=(1,2)$, $f(A,1)\cdot f(A,2)=3\cdot 3=9$
  • When $A=(1,3)$, $f(A,1)\cdot f(A,2)=2\cdot 2=4$
  • When $A=(2,1)$, $f(A,1)\cdot f(A,2)=3\cdot 3=9$
  • When $A=(2,2)$, $f(A,1)\cdot f(A,2)=1\cdot 3=3$
  • When $A=(2,3)$, $f(A,1)\cdot f(A,2)=1\cdot 4=4$
  • When $A=(3,1)$, $f(A,1)\cdot f(A,2)=2\cdot 2=4$
  • When $A=(3,2)$, $f(A,1)\cdot f(A,2)=1\cdot 4=4$
  • When $A=(3,3)$, $f(A,1)\cdot f(A,2)=1\cdot 2=2$

Therefore, the answer is $4+9+4+9+3+4+4+4+2=43$.

Sample 2
Input
1 1 1
Output
2
  • When $A=(1,1)$, $f(A,1)=2$

Therefore, the answer is $2$.

Sample 3
Input
40 40 40
Output
801530328

Find the answer modulo $998244353$.

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