题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3398
题意：
约翰要带N(1≤N≤100000)只牛去参加集会里的展示活动，这些牛可以是牡牛，也可以是牝牛。
牛们要站成一排。但是牡牛是好斗的，为了避免牡牛闹出乱子，约翰决定任意两只牡牛之间至少要有K(0≤K<N)只牝牛。
请计算一共有多少种排队的方法。所有牡牛可以看成是相同的，所有牝牛也一样。答案对5000011取模。
题解：
表示状态：
dp[i] = num of ways
表示考虑到位置i，并且在这里放了牡牛的方案数。
找出答案：
ans = ∑(dp[i]) + 1
因为不放牡牛也算一种方案，所以最后+1。
如何转移：
dp[i] = ∑ dp[0 to i-k-1] + 1
上一次放牡牛的位置至少在i前面k+1个牛的位置。
或者这是第一次放牡牛，所以+1。
优化：
前缀和优化。
AC Code:
// state expression:
// dp[i] = num of ways
// i: last pos of cow2
//
// find the answer:
// sigma dp[i] + 1
//
// transferring:
// dp[i] = sigma dp[0 to i-k-1] + 1
//
// boundary:
// set dp = 0
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 100005
#define MOD 5000011 using namespace std; int n,k;
int ans;
int dp;
int sum[MAX_N]; void read()
{
cin>>n>>k;
} void solve()
{
sum[]=;
ans=;
for(int i=;i<=n;i++)
{
dp=;
if(i-k->=) dp=(dp+sum[i-k-])%MOD;
sum[i]=(sum[i-]+dp)%MOD;
ans=(ans+dp)%MOD;
}
} void print()
{
cout<<ans<<endl;
} int main()
{
read();
solve();
print();
}