白云在健身，每秒可以走1米或跑k米，并且不能连续两秒都在跑。
当它的移动距离在[L,R]之间时，可以选择结束锻炼。
问有多少种方案结束。
爬楼梯模型：dp[n]=dp[n-1]+dp[n-1-k]
#include <iostream> #include <cstdio> using namespace std; #define mod 1000000007 int q,k; long long dp[100005]; int main() { scanf("%d%d",&q,&k); for(int i=1;i<k;i++) dp[i]=1; dp[k]=2; dp[k+1]=3; for(int i=k+2;i<=100001;i++) { dp[i]=(dp[i-1]+dp[i-k-1])%mod; } for(int i=2;i<=100001;i++) { dp[i]=dp[i-1]%mod+dp[i]%mod; } while(q--){ int a,b; scanf("%d%d",&a,&b); long long ans=(dp[b]-dp[a-1])%mod; printf("%lld\n",ans); } return 0; }
原文：https://www.cnblogs.com/Fy1999/p/9683106.html