Hà Nội [yukicoder 1184]

https://yukicoder.me/problems/no/1184

解説

https://yukicoder.me/submissions/536895

星1.5であるが、割と難しい問題に見える。
だが、理由があって星1.5になっているのであって、なるべくシンプルに考察を進める。

面倒な条件は何か

L枚以下の板なら1回でまとめて動かすことができるという条件が面倒に見える。
これがL=1の場合、つまり、一般的なハノイの塔問題であれば答えはどうなるだろう。
こっちの計算もややこしいのだが、漸化式あたりで真面目に考えてもいいし、有名問題なのでググってもいい。
ハノイの塔のルールと最短手数 | 高校数学の美しい物語
コンテスト的にはググって出てくればそれでいい。2^n - 1

ハノイの塔に帰着できないか？

これは割とある問題であるが、何か色々頑張ると既知の問題に帰着できて後は計算するだけという問題がある。
今回も、ハノイの塔の公式が使えるようにチューニングしよう。
L枚以下の板なら1回でまとめて動かせるのであれば、あえてバラバラに動かす必要もなく、1グループとして扱っていい（未証明）。
なので、何グループできるかというと、N÷Lの切り上げ個数のグループなので、これをNとすれば、Lは1として考えることができる。
あとは、公式に載せて計算するだけ。

注意

累乗計算は10¹⁸ではTLEするので、繰り返し二乗法を用いること。

ll N, L;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> L;

    N = (N + L - 1) / L;

    mint ans = (mint(2) ^ N) - 1;
    cout << ans << endl;
}