No.2351 Butterfly in Summer
タグ : / 解いたユーザー数 193
作問者 :
AngrySadEight
/ テスター :
👑 
p-adic
kumakuma
問題文
yuki 国に生息する蝶はいずれも羽が $N$ 個の部分に分かれており，そのそれぞれに対して $K$ 種類の候補の色の中から等確率で $1$ 種類の色がついています．
この蝶の羽のうち，$N-1$ 個の部分の色がすべて同じであり，残りの $1$ 個の部分だけほかの $N-1$ 個の部分とは色が異なる確率を，以下の注記に示すように $\bmod 998244353$ で求めてください．
注記
求める値は有理数となることが証明できます．また，この問題の制約下では，その値を互いに素な $2$ つの整数 $P,Q$ を用いて $\frac{Q}{P}$ と表したとき，$RP \equiv Q \pmod{998244353}$ かつ $0 \leq R < 998244353$ を満たす整数 $R$ がただ一つ存在することが証明できます．この $R$ を出力してください．
制約
- 入力はすべて整数である．
- $3 \leq N \leq 10^5$
- $2 \leq K \leq 10^5$
入力
入力は以下の形式で標準入力から与えられる．
$N$ $K$
出力
答えを注記に示したように $\bmod 998244353$ で出力せよ．
サンプル
サンプル1
入力
3 2
出力
249561089
$3$ 個の部分に塗る色の組 $(c_1, c_2, c_3)$は，以下の $8$ 個です．
- $(c_1, c_2, c_3) = (1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1), (2,2,2)$
このうち，条件を満たす色の組は，$(1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1)$ の $6$ 個です．
したがって，求める確率は $\frac{6}{8} = \frac{3}{4}$ です．$4 \times 249561089 \equiv 3 \pmod{998244353}$ であるため，$249561089$ を出力してください．
サンプル2
入力
4 2
出力
499122177
$4$ 個の部分に塗る色の組 $(c_1, c_2, c_3, c_4)$は，全部で $16$ 個です．このうち，条件を満たす色の組は，$(1,1,1,2), (2,1,2,2)$ など，全部で $8$ 個あります．
したがって，求める確率は $\frac{8}{16} = \frac{1}{2}$ です．$2 \times 499122177 \equiv 1 \pmod{998244353}$ であるため，$499122177$ を出力してください．
サンプル3
入力
16 2017
出力
62053606
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。