题目:https://vjudge.net/contest/326867#problem/B
题意:有很多个蛋糕,现在你有两种吃蛋糕的吃法,一次吃一个,定为A,一次吃k个定为B,然后问你吃m个蛋糕有多少种方法,每次询问一个区间的和
思路:这个很容易看出来是一个DP,我们可以dp[i]=dp[i-1]+dp[i-k] 代表当前我放A还是放B,然后一次询问一个区间的话我们直接求一个前缀和即可
#include<bits/stdc++.h> #define maxn 100005 #define mod 1000000007 using namespace std; typedef long long ll; ll t,k; ll dp[maxn]; ll sum[maxn]; int main(){ cin>>t>>k; dp[0]=1; for(int i=1;i<maxn;i++){ dp[i]=dp[i-1]; if(i-k>=0) dp[i]=(dp[i]+dp[i-k])%mod; } for(int i=1;i<maxn;i++){ sum[i]=(sum[i-1]+dp[i])%mod; } ll x,y; while(t--){ cin>>x>>y; cout<<(sum[y]-sum[x-1]+mod)%mod<<" "; } }