問題一覧 > 通常問題

No.1967 Sugoroku Optimization

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 57
作問者 : rianoriano / テスター : milkcoffeemilkcoffee
2 ProblemId : 7469 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-20 20:19:54

問題文

無限に続くマス目に $0,1,2,...$ と順に番号が振られており、あなたは最初 $0$ のマスにいます。 あなたはこれから、ターンごとに好きな正の整数 $a$ を $1$ つ選び、以下の行動を行います。

  • $1$ 以上 $a$ 以下の整数が等確率で出るルーレットを回し、その結果出た数字の分だけマスを進む。
ここで、$K$ 回以内のターンでちょうど $N$ のマスに止まることができればあなたの勝利とします。 ターンごとに最適な選択をした場合のあなたの勝率はいくらでしょうか。

この確率は有理数であることが証明できますので、$\mathrm{mod}$ $998244353$ で答えてください。 厳密には、答えを既約分数で $P/Q$ としたとき、$P\equiv Q\times R$ ($\mathrm{mod}$ $998244353$) となる $0$ 以上 $998244353$ 未満の整数 $R$ を答えてください。

入力

$N\ \ K$

  • $2\leq N \leq 2000$
  • $1 \leq K \leq N$
  • 入力は全て整数である

出力

上述の $R$ の値を出力してください。 最後に改行してください。

サンプル

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

$2$ ターン以内に、マス $3$ にちょうどたどり着けば勝利となります。この時の最適な戦略の $1$ つは以下の通りです。
まず、初めに最大値 $3$ のルーレットを回します。$2$ 以上が出れば、確実に勝利できます。$1$ が出た場合、次のターンには最大値 $2$ のルーレットを回します。 このとき、勝利できないのは、二度続けて $1$ が出てしまった場合のみで、その確率は $1/3 \times 1/2 = 1/6$ です。
したがって、勝率は $5/6$ ですので、$\mathrm{mod}$ $998244353$ では上記の答えになります。

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

毎回 $1$ しか出ないルーレットを使えば確実に勝利できます。

サンプル3
入力
1994 1210
出力
29843801

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