問題一覧 > 通常問題

No.1856 Mex Sum 2

レベル : / AI推定難易度 : 2125 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 35
作問者 : 蜜蜂 / テスター : Mitarushi
お気に入りにしたユーザー ProblemId : 6243 / 自分の提出
問題文最終更新日: 2022-02-23 20:47:19
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 333 (灘高入試コンテスト2022) (順位表) の他の問題:

Problem Statement

For an integer sequence $A$ of length $N$ whose elements are each between $0$ and $M$, inclusive, define $f(A)$ as follows.

  • The sum of $\mathrm{mex} (A')$ over all of the $2^N-1$ possible non-empty subsequences $A'$ of $A$. (A subsequence of $A$ is an integer sequence obtained by choosing and deleting some $0$ or more elements of $A$ and arranging the remaining elements in their original order.)
    • Here, for an integer sequence $X$, $\mathrm{mex} (X)$ is the smallest integer greater than or equal to $0$ that is not equal to any element of $X$. For example, $\mathrm{mex} \left( \left( 0,1,7 \right) \right) = 2,\mathrm{mex} \left( \left( 2022,77 \right) \right) = 0$.

There are $(M+1)^N$ possible sequences $A$. Find the sum of $f(A)$ over all of them, modulo $998244353$.

Input

$N\ \ M$

  • $1 \leq N \leq 2000$
  • $1 \leq M \leq 10^9$
  • All inputs are integers.

Output

Print the sum of $f(A)$ over all $(M+1)^N$ possible sequences $A$, modulo $998244353$, followed by a newline.

Sample

Sample 1
Input
2 1
Output
9

The $(1+1)^2=4$ possible sequences $A$ and their corresponding values of $f(A)$ are as follows.

  • When $A=(0,0)$, $f(A)=3$.
  • When $A=(0,1)$, $f(A)=3$.
  • When $A=(1,0)$, $f(A)=3$.
  • When $A=(1,1)$, $f(A)=0$.
Their sum is $9$.

Sample 2
Input
3 2
Output
127

For example, when $A=( 0,0,0 )$, $f(A)=7$.

Sample 3
Input
100 99
Output
275874233

Print the value modulo $998244353$.

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