A21091 公交车路线 全站首发题解

#include <iostream>
#include <vector>
#include <numeric>

void solve() {
    int n;
    std::cin >> n;

    std::vector<long long> dp_counts(4, 0);

    dp_counts[0] = 1;

    for (int i = 1; i < n; ++i) {
        std::vector<long long> next_dp_counts(4, 0);

        next_dp_counts[0] = dp_counts[1];
        next_dp_counts[1] = (dp_counts[0] * 2 + dp_counts[2]);
        next_dp_counts[2] = (dp_counts[1] + dp_counts[3]);
        next_dp_counts[3] = dp_counts[2];

        dp_counts[0] = next_dp_counts[0] % 1000;
        dp_counts[1] = next_dp_counts[1] % 1000;
        dp_counts[2] = next_dp_counts[2] % 1000;
        dp_counts[3] = next_dp_counts[3] % 1000;
    }

    std::cout << dp_counts[3] << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}