本文共 731 字，大约阅读时间需要 2 分钟。

题意

白云一次可以走1米或者跑k米，但是不能连续跑，问白云到达区间 [L, R]一共有几种方法

AC

• dp
  dp的意义是记录当前的方案数
  0表示走到当前位置的方案数
  1表示跑到当前位置的方案数
  

using namespace std;int inf = 0x3f3f3f3f;int mod = 1e9 + 7;ll dp[N][2], ans[N];int main(){#ifndef ONLINE_JUDGE    freopen("in.txt", "r", stdin);#endif    int q, k;    scanf("%d %d", &q, &k);    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 - k >= 0) {            dp[i][1] = dp[i - k][0] % mod;        }    }    for (int i = 1; i < N; ++i) {        ans[i] = ans[i - 1] + dp[i][1] + dp[i][0];    }    for (int i = 0; i < q; ++i) {        int l, r;        scanf("%d%d", &l, &r);        printf("%lld\n", (ans[r] - ans[l - 1]) % mod);    }    return 0;}