問題一覧 > 通常問題

No.1757 Many Many Cards

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 29
作問者 : PCTprobabilityPCTprobability / テスター : NyaanNyaanNyaanNyaan tokusakuraitokusakurai
2 ProblemId : 7231 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-20 20:44:20

問題文

PCT 君は以下のような問題を作りました。

Many Cards

$X$ 枚のカードがあり、$i$ 枚目のカードには $A_i$ か $B_i$ を書き込むことができます。

カードに書き込む整数を自由に決められる時のカードに書かれた整数の種類数の最大値を求めてください。

この問題は Nyaan さんにはあまりにも簡単だったため、PCT 君は問題を以下のように変更しました。

Many Many Cards

$N,M$ が与えられます。Many Cards の入力の内、$X=N$ かつ $A_i,B_i$ が整数かつ $1 \le A_i,B_i \le M$ を満たすものは $M^{2N}$ 通りありますが、その全てに対する解の総和を $998244353$ で割ったあまりを求めてください。

Many Many Cards を解いてください。

制約

  • 入力は全て整数である。
  • $1 \le N,M \le 2 \times 10^5$

入力

$N\ M$

出力

答えを $1$ 行に出力してください。

サンプル

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

例えば、$A=(1,2),B=(2,2)$ の場合は $1$ 枚目のカードに $1$、$2$ 枚目のカードに $2$ を書き込むことで $2$ 種類の整数を書き込むことができます。

また、$3$ 種類以上の整数を書き込めないことが証明できるので、この場合の解は $2$ です。

あり得る入力 $81$ 通り全てに対する解の総和は、$159$ となります。

サンプル2
入力
5 4
出力
3941788

サンプル3
入力
2021 1120
出力
458917605

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