题解 CF474D 【Flowers】

一道入门DP

设f[i]表示到 i 个蛋糕的方案数

由题可知f[i] 可以由 f[i - 1] （只吃1 个）,f[i - k]（i - k > 0,吃k个）转移过来

然后用sum前缀和维护一下，就可以O(1)的回答询问了

void solve() {
    f[0] = 1;
    rep(i, 1, 100001) {
        f[i] = f[i - 1];
        if(i >= k) f[i] = (f[i] + f[i - k]) % Mod;
        sum[i] = (sum[i - 1] + f[i]) % Mod;
    }
    while(N--) {
        int l = Read(), r = Read();
        printf("%lld\n", (sum[r] - sum[l - 1] + Mod) % Mod);
    }
}