はまやんはまやんはまやん

hamayanhamayan's blog

Jumping Kangaroo [yukicoder 997]

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

前提知識

解説

https://yukicoder.me/submissions/433408

Wの倍数で白石を踏んでいく必要がある。
例えば、白石を必ず踏んでいく必要がある場合は、白石間の組み合わせを計算して、K乗すれば答えが得られる。
これを発展させて考えると、ある白石が踏まれるのは、1つ前の白石が踏まれるか、2つ前の白石が踏まれる場合である。
以下のようなdpが思いつく。
dp[i] := i番目の白石を踏む組み合わせ
dp[i] = dp[i - 1] * (白石間の組み合わせ) + dp[i - 2] * (1つ白石を飛ばした時の白石間の組み合わせ)
この計算は行列累乗で高速化できるので、これで計算可能。

あとは、(白石間の組み合わせ)と(1つ白石を飛ばした時の白石間の組み合わせ)が分かればいい。
これもDPを使うことで計算可能。
dp[cu] := cu番目の石に到達するためのジャンプの組み合わせ
これは一般的な組み合わせDPで可能。
すると、
(白石間の組み合わせ) = dp[W]
(1つ白石を飛ばした時の白石間の組み合わせ) = dp[2W]-dp[W]dp[W]
となるので解決。

int N, W, A[101]; ll K;
mint dp[201];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> W >> K;
    rep(i, 0, N) cin >> A[i];

    dp[0] = 1;
    rep(cu, 0, W * 2) rep(i, 0, N) dp[cu + A[i]] += dp[cu];
    dp[2 * W] -= dp[W] * dp[W];

    int ans = solveLinearRecurrenceFormula({ dp[0].get(), dp[W].get() }, { dp[W].get(), dp[2 * W].get() }, K);
    cout << ans << endl;
}