题目描述

牡 mǔ，畜父也。牝 pìn，畜母也。 ——《说文解字》

约翰要带 N 只牛去参加集会里的展示活动，这些牛可以是牡牛，也可以是牝牛。牛们要站成一排，但是牡牛是好斗的，为了避免牡牛闹出乱子，约翰决定任意两只牡牛之间至少要有 K 只牝牛。

请计算一共有多少种排队的方法，所有牡牛可以看成是相同的，所有牝牛也一样，答案对 5000011 取模。

样例

4 2

输出

6

算法1

(前缀和加dp) $O(n)$

···
首先f[i]表示所有长度为i的且最后一位是1的字符串的数量,它如果i是1，那么只能是i-k-1,....1,这些位置可能是1,于是f[i]=f[i-k-1]+....f[1],把后面表示为s[i-k-1];
其次有可能i前面的所有字符都不是1,就是全是0,那么用f[0]=1，表示全是0的方案数，也刚好是1,然后就f[i]=f[i-k-1]+....f[1]+f[0],于是s是从0开始计数的。
那长度为i的方案数就是s[i]=f[0]+....f[i]=s[i-1]+f[i];可以维护一个前缀和将时间复杂度降下来

···

C++ 代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int N =100010,mod=5000011;
int n,m;
int s[N],f[N];
int main()
{
    scanf("%d%d",&n,&m);
    s[0]=f[0]=1;
    for(int i=1;i<=n;i++)
    {

        f[i]=s[max(i-m-1,0)];
        s[i]=(s[i-1]+f[i])%mod;
    }
    cout<<s[n]<<endl;
    return 0;
}