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; }