No.1757 Many Many Cards
タグ : / 解いたユーザー数 41
作問者 :
PCTprobability
/ テスター :
NyaanNyaan
tokusakurai
問題文
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もしくは右上の雲マークをクリックしてアカウントを作成してください。