考えたこと

素朴には、互換を繰り返して1をKにする方法それぞれについて、空いてるところを何通りで埋められるか考える

これは間に合わなさそう

横8縦100

1行あたりの線の引き方は2^7より少ない

最初に「iがjに行くのは何通りか」を愚直に数え上げておく

「a行目で1がbにあるのは何通りか」でDPする

最後にK番目を読めば良い

余談: 今回は8×8×100だから必要を感じないんだけど、もっと大きい場合。遷移行列の累乗だからダブリングできる

公式解説OK

公式解説は遷移確率を前計算しないで全探索しているが、それでも十分間に合う

小さい値で試してみれば実はフィボナッチ数列が出てくることに気づけたかも知れない