問題一覧 > 通常問題

No.2084 Mex Subset For All Sequences

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 17
作問者 : taiga0629kyoprotaiga0629kyopro / テスター : nok0nok0 👑 ygussanyygussany
4 ProblemId : 8506 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-17 23:46:59

問題文

taiga 君は次のような問題を作りました。

Mex Subset

長さ $N$ の整数列 $A$ が与えられます。$\lbrace 1,2,\dots,N \rbrace$ の空でない部分集合 $S=\lbrace S_1,S_2,\dots,S_k \rbrace$ は $2^N-1$ 個ありますが、その全てについて $\mathrm{mex}(A_{S_1},A_{S_2},\dots,A_{S_k})$ を計算し、その総和を求めてください。

ただし、$\mathrm{mex}(X_1,X_2,\dots,X_k)$ で、$X_1,X_2,\dots,X_k$ に含まれない最小の非負整数を表します。

長さが $N$ で、各要素が $0$ 以上 $M$ 未満の整数である数列 $A$ は $M^N$ 個ありますが、その全てに対して問題 "Mex Subset" を解いたときの答えの総和を $998244353$ で割った余りを出力してください。

入力

$N$ $M$

  • $1 \le N \le 10^5$
  • $1 \le M \le 10^5$
  • 入力は全て整数
  • 出力

    $M^N$ 個の数列 $A$ 全てに対する "Mex Subset" の答えの総和を $998244353$ で割った余りを出力してください。

    サンプル

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

    例えば、$A=(0,1)$ のとき、"Mex Subset" の答えは、 $\mathrm{mex}(A_1)+\mathrm{mex}(A_2)+\mathrm{mex}(A_1,A_2)=1+0+2=3$ となります。

    サンプル2
    入力
    6 6
    出力
    1840825

    サンプル3
    入力
    92 60
    出力
    495606575

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