水博客。
A.run
题意就是一个人一秒可以走1步或者跑K步，不能连续跑2秒，他从0开始移动，移动到[L,R]的某一点就可以结束。问一共有多少种移动的方式。
个人感觉是带约束条件的超级楼梯问题。说是dp其实就是递推吧。只要连续的两秒不是跑的就可以。所以在已经跑了i步的时候，直接考虑最后一步是跑的还是走的就可以了。
所以公式就是dp[i]=dp[i-1]+dp[i-1-k];然后前缀和预处理一下，直接从L的for到R的就可以了。
反正乱七八糟就出来了。现在写题写的脑子都没了。
代码:
//A
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
const ll mod=;
ll dp[maxn],ans[maxn];
void init(int k)
{
for(int i=;i<k;i++)
dp[i]=;
dp[k]=;
for(int i=k+;i<maxn;i++)
dp[i]=(dp[i-]+dp[i-k-])%mod;
for(int i=;i<maxn;i++)
ans[i]=(ans[i-]+dp[i])%mod;
}
int main()
{
int q,k;
scanf("%d%d",&q,&k);
init(k);
while(q--){
int l,r;
scanf("%d%d",&l,&r);
printf("%lld\n",(ans[r]-ans[l-]+mod)%mod);
}
}
Come on，BABY.
