碎碎念

碎碎念
https://ac.nowcoder.com/acm/contest/3006/F

本题涉及动态规划
针对第i次喊叫，有AC和RJ两种情况，分别用DP[i][0]和DP[i][1]表示
可划分为两种情况
i<x时候，只能是AC,DP[i][0]=DP[i-1]0此时DP[i-1][1]是0
i>=x时，分两种情况：
1：第i次是AC，则DP[i][0]=DP[i-1][0]+DP[i-1][1]
2：第i次是RJ，则DP[i][1]=DP[i-x][0] (RJ前一次必定是AC)
临界条件：DP[0][0]=1,DP[0][1]=0;

DP[0][0]=1,DP[0][1]=0;
for (int i = 1; i < N; i++) {
        DP[i][0] = (DP[i - 1][0] + DP[i - 1][1]) % mod;
        if (i >= x) {
            DP[i][1] = DP[i - x][0];
        }
}

有Q次询问，可考虑前缀和记录总方案数

DP[i][2] = (DP[i][0] + DP[i][1]) % mod;
DP[i][2] += DP[i - 1][2];
DP[i][2] %= mod;

代码如下

#pragma warning (disable :4996)
#include <iostream>
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const double eps = 1e-7;
const int N = 1e5 + 10;
int x, Q;
ll DP[N][4];
int main() {
    scanf("%d", &x);
    DP[0][0] = 1;
    for (int i = 1; i < N; i++) {
        DP[i][0] = (DP[i - 1][0] + DP[i - 1][1]) % mod;
        if (i >= x) {
            DP[i][1] = DP[i - x][0];
        }
        DP[i][2] = (DP[i][0] + DP[i][1]) % mod;
        DP[i][2] += DP[i - 1][2];
        DP[i][2] %= mod;
    }
    scanf("%d", &Q);
    while (Q--) {
        int le, r;
        scanf("%d %d", &le, &r);
        ll ans = (DP[r][2] - DP[le - 1][2] + mod) % mod;
        cout <<  ans<< endl;
    }
}