No.1967 Sugoroku Optimization
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 78
作問者 :
riano
/ テスター :
milkcoffee
タグ : / 解いたユーザー数 78
作問者 :
riano
/ テスター :
milkcoffee
問題文最終更新日: 2022-05-20 20:19:54
問題文
無限に続くマス目に $0,1,2,...$ と順に番号が振られており、あなたは最初 $0$ のマスにいます。 あなたはこれから、ターンごとに好きな正の整数 $a$ を $1$ つ選び、以下の行動を行います。
- $1$ 以上 $a$ 以下の整数が等確率で出るルーレットを回し、その結果出た数字の分だけマスを進む。
この確率は有理数であることが証明できますので、$\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もしくは右上の雲マークをクリックしてアカウントを作成してください。