問題一覧 > 通常問題

No.1184 Hà Nội

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 226
作問者 : kaagekaage / テスター : penguinmanpenguinman
8 ProblemId : 4922 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-22 14:06:18

問題文

「ハノイの塔」というゲームを知っていますか?僕は知っています。
「ハノイの塔」は以下のようなゲームです。

$N$ 枚の、大きさの互いに異なる板が、上から大きさの昇順に塔に刺さっています。
今この板が刺さっている塔を塔 $A$ として、塔 $B$ にこの板をすべて移すことを考えます。
塔 $C$ を補助に使うことができますが、板は次の条件を満たすように移動させなければいけません。
  • 小さい板の上にそれより大きい板を載せてはいけない。つまり、板の大きさがどの塔でも上から昇順になるように板を積まなくてはならない。
  • それぞれの塔のいちばん上にある板しか動かせない。
  • 板をまとめて複数枚動かすことはできない。
これが通常のハノイの塔のルールですが、それではつまらないので、今回は、それぞれの塔のいちばん上に、上から大きさの昇順に並んでいる $L$ 枚以下の板なら $1$ 回でまとめて動かしてよいことにします。
このとき、すべての板を移し替えるまでに必要な操作の回数は何回でしょうか。
操作の最小回数を $998244353$ で割った余りを求めてください。

入力

$N\ L$

  • $1\leq N,L\leq 10^{18}$
  • 入力は全て整数

出力

必要な最小操作回数を $998244353$ で割った余りを1行に出力してください。
余りの最小値ではなく、最小値の余りを求めることに注意してください。

サンプル

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

次のように操作を行えばいいです。

  • $1$ 枚目の板を塔 $C$ に動かす。
  • $2,3$ 枚目の板をまとめて塔 $B$ に動かす。
  • $1$ 枚目の板を塔 $B$ に動かす。

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

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