問題一覧 > 通常問題

No.2936 Sum of Square of Mex

レベル : / AI推定難易度 : 2150 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 21
作問者 : nouka28 / テスター : tnodino hirayuu_yc mymelochan kusirakusira uruzunyaa
お気に入りにしたユーザー ProblemId : 11475 / 自分の提出
問題文最終更新日: 2024-10-12 10:54:27
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
第3回緑以下コンテスト エキストラ (順位表) の他の問題:

Problem Statement

You are given a positive integer $N$ and a non-negative integer $M$.

There are $(M+1)^N$ sequences $A$ of non-negative integers of length $N$ satisfying $0\leq A_i\leq M$.

Find the sum of $\mathrm{mex}(A)^2$ over all of them, modulo $998244353$.

Constraints

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

Input

$N$ $M$

The input is given from Standard Input in the following format.

Output

Output the answer.

Sample

Sample 1
Input
2 2
Output
11
  • When $A=(0,0)$, $\mathrm{mex}(A)^2=1^2=1$.
  • When $A=(0,1)$, $\mathrm{mex}(A)^2=2^2=4$.
  • When $A=(0,2)$, $\mathrm{mex}(A)^2=1^2=1$.
  • When $A=(1,0)$, $\mathrm{mex}(A)^2=2^2=4$.
  • When $A=(1,1)$, $\mathrm{mex}(A)^2=0^2=0$.
  • When $A=(1,2)$, $\mathrm{mex}(A)^2=0^2=0$.
  • When $A=(2,0)$, $\mathrm{mex}(A)^2=1^2=1$.
  • When $A=(2,1)$, $\mathrm{mex}(A)^2=0^2=0$.
  • When $A=(2,2)$, $\mathrm{mex}(A)^2=0^2=0$.

Therefore, the answer is $1+4+1+4+0+0+1+0+0=11$.

Sample 2
Input
1 0
Output
1
Sample 3
Input
31415 926535897
Output
170588663

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