题解 | 小红蹦跳蹦跳

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
using ll = long long;
using vi = vector<int>;
const ll mod = 1000000007;

void solve() {
    int n;cin >> n;
    vi dp(n + 1);
    vi dp2(n + 1);
    int sum1 = 0, sum2 = 0, sum3 = 0, sum4 = 0;
    for (int i = 1;i <= n;i++) {
        if (i % 2 == 1) {
            dp[i]++;
            dp[i] %= mod;
            dp[i] += sum4;
            dp[i] %= mod;
            dp2[i] += sum1;
            dp2[i] %= mod;
        }
        else {
            dp2[i]++;
            dp2[i] %= mod;
            dp[i] += sum3;
            dp[i] %= mod;
            dp2[i] += sum2;
            dp2[i] %= mod;
        }
        if (i % 2 == 1) {
            sum1 += dp[i];
            sum3 += dp2[i];
            sum1 %= mod;
            sum3 %= mod;
        }
        else {
            sum2 += dp[i];
            sum4 += dp2[i];
            sum2 %= mod;
            sum4 %= mod;
        }
    }
    cout << (dp[n] + dp2[n]) % mod << endl;
}

/*

*/

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; i++) {
        //cout << "----Test " << i << "----" << endl;
        solve();
    }
    return 0;
}

前缀和优化dp，定义dp1数组为奇数步结尾，dp2为偶数步结尾，dp1[i]可以由前面的与当前i奇偶性性不同的dp2转移过来，dp2[i]可以由前面与当前i奇偶性相同的dp1转移过来，考虑到数据范围1e6，不能n方，考虑前缀和优化，记录每一个奇偶性以及dp1和dp2，四个前缀和优化。手推前六个数可以手搓递推式dp1是1 0 2 1 3 4，dp2是0 1 1 1 3 2，最后相加即是答案。