問題一覧 > 通常問題

No.2245 Second Smallest

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 : noya2noya2 / テスター : shobonvipshobonvip 👑 NachiaNachia
4 ProblemId : 9050 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-10 01:28:43

問題文

縦 $H$ 行、横 $W$ 列のグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ で表します。 マス $(i,j)$ には $0$ 以上 $1$ 以下の実数が一様ランダムに、各マスごとに独立に書かれています。

noya 君はマス $(1,1)$ にいて、右または下に隣接するマスへの移動を繰り返してマス $(H,W)$ に到達したいです。 このとき通ったマス( $(1,1),(H,W)$ を含む )に書かれた実数のうち 重複を含めて $2$ 番目に小さい実数を $x$ とすると、 noya 君が得るスコアは $x^K$ です。

noya 君が移動経路のスコアができるだけ小さくなるように移動するとき、 スコアの期待値を $\bmod 998244353$ で求めてください。( 注記参照 )

注記

求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、 その値を互いに素な $2$ つの整数 $P,Q$ を用いて $\dfrac{P}{Q}$ と表したとき、 $R\times Q\equiv P\pmod{998244353}$ かつ $0\le R\lt 998244353$ を満たす整数 $R$ が ただ一つ存在することが証明できます。この $R$ を求めてください。

制約

  • 入力はすべて整数
  • $2\le H,W\le 3\times 10^4$
  • $1\le K\le 3\times 10^4$

入力

$H$ $W$ $K$

出力

noya 君が得るスコアの期待値を $\bmod 998244353$ で求め、出力してください。

サンプル

サンプル1
入力
2 2 1
出力
632221424

求める期待値は $\dfrac{13}{30}$ です。

サンプル2
入力
3 4 2
出力
764290182

求める期待値は $\dfrac{214}{5005}$ です。

サンプル3
入力
314 159 265
出力
369907178

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