問題一覧 > 通常問題

No.2084 Mex Subset For All Sequences

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 23
作問者 : taiga0629kyopro / テスター : nok0 ygussany
お気に入りにしたユーザー ProblemId : 8506 / 自分の提出
問題文最終更新日: 2022-09-17 23:46:59
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 361 (順位表) の他の問題:

Problem Statement

Taiga created the following problem.

Mex Subset

You are given an integer sequence $A$ of length $N$. There are $2^N-1$ non-empty subsets $S=\lbrace S_1,S_2,\dots,S_k \rbrace$ of $\lbrace 1,2,\dots,N \rbrace$. For all of them, compute $\mathrm{mex}(A_{S_1},A_{S_2},\dots,A_{S_k})$ and find the sum.

Here, $\mathrm{mex}(X_1,X_2,\dots,X_k)$ denotes the smallest non-negative integer not contained in $X_1,X_2,\dots,X_k$.

There are $M^N$ sequences $A$ of length $N$ whose elements are integers at least $0$ and less than $M$. Solve the problem "Mex Subset" for all of them, and output the sum of the answers modulo $998244353$.

Input

$N$ $M$

  • $1 \le N \le 10^5$
  • $1 \le M \le 10^5$
  • All inputs are integers.

    • Output

    Output the sum of the answers to "Mex Subset" over all $M^N$ sequences $A$, modulo $998244353$.

    Sample

    Sample 1
    Input
    2 3
    Output
    13

    For example, when $A=(0,1)$, the answer to "Mex Subset" is $\mathrm{mex}(A_1)+\mathrm{mex}(A_2)+\mathrm{mex}(A_1,A_2)=1+0+2=3$.

    Sample 2
    Input
    6 6
    Output
    1840825

    Sample 3
    Input
    92 60
    Output
    495606575

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