DOJ-team-match 8-吃蛋糕

1698988100185

放张图自己体会(doge

类似于爬楼梯的递推题

动态转移方程，或者说递推式：

dp[i]=dp[i-1]+dp[i-k]

其中$i≥k$

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
long long t,k,a,b;
long long dp[100010],sum[100010];
int main()
{
    cin>>t>>k;
    dp[0]=1;
    for(int i=1;i<=100000;i++)
    {
        dp[i]=dp[i-1]%mod;
        if(i>=k) dp[i]=(dp[i-1]+dp[i-k])%mod;
        sum[i]=sum[i-1]+dp[i];
    }
    while(t--)
    {
        cin>>a>>b;
        cout<<(sum[b]-sum[a-1]+mod)%mod<<endl;
    }
    return 0;
}

注意在输出时为避免因取模而出现的$sumb>suma$，需要加上一个$mod$以避免负数

我就因为这个错了快20次[开心开心]