問題一覧 > 通常問題

No.2351 Butterfly in Summer

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 200
作問者 : 👑 AngrySadEight / テスター : 👑 p-adic kumakuma
1 ProblemId : 9440 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-05-12 09:54:09

問題文

yuki 国に生息する蝶はいずれも羽が NN 個の部分に分かれており，そのそれぞれに対して KK 種類の候補の色の中から等確率で 11 種類の色がついています．

この蝶の羽のうち，N−1N-1 個の部分の色がすべて同じであり，残りの 11 個の部分だけほかの N−1N-1 個の部分とは色が異なる確率を，以下の注記に示すように  mod 998244353\bmod 998244353 で求めてください．

注記

求める値は有理数となることが証明できます．また，この問題の制約下では，その値を互いに素な 22 つの整数 P,QP,Q を用いて QP\frac{Q}{P} と表したとき，RP≡Q(mod998244353)RP \equiv Q \pmod{998244353} かつ 0≤R<9982443530 \leq R < 998244353 を満たす整数 RR がただ一つ存在することが証明できます．この RR を出力してください．

制約

  • 入力はすべて整数である．
  • 3≤N≤1053 \leq N \leq 10^5
  • 2≤K≤1052 \leq K \leq 10^5

入力

入力は以下の形式で標準入力から与えられる．

NN KK

出力

答えを注記に示したように  mod 998244353\bmod 998244353 で出力せよ．

サンプル

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

33 個の部分に塗る色の組 (c1,c2,c3)(c_1, c_2, c_3)は，以下の 88 個です．

  • (c1,c2,c3)=(1,1,1),(1,1,2),(1,2,1),(1,2,2),(2,1,1),(2,1,2),(2,2,1),(2,2,2)(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)(1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1) の 66 個です．

したがって，求める確率は 68=34\frac{6}{8} = \frac{3}{4} です．4×249561089≡3(mod998244353)4 \times 249561089 \equiv 3 \pmod{998244353} であるため，249561089249561089 を出力してください．

サンプル2
入力
4 2
出力
499122177

44 個の部分に塗る色の組 (c1,c2,c3,c4)(c_1, c_2, c_3, c_4)は，全部で 1616 個です．このうち，条件を満たす色の組は，(1,1,1,2),(2,1,2,2)(1,1,1,2), (2,1,2,2) など，全部で 88 個あります．

したがって，求める確率は 816=12\frac{8}{16} = \frac{1}{2} です．2×499122177≡1(mod998244353)2 \times 499122177 \equiv 1 \pmod{998244353} であるため，499122177499122177 を出力してください．

サンプル3
入力
16 2017
出力
62053606

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