$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

1. f[i] 表示最后一个 1 在第 i 位，s[i] 是 f[i] 的前缀和
2. f[i] = f[0] + f[1] + ... + f[i - k - 1] = s[i - k - 1]
3. s[i] = s[i - 1] + f[i] = s[i - 1] + s[i - k - 1]

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 100010, mod = 5000011;

int n,k;
int s[N];

int main()
{
    cin>>n>>k;

    s[0]=1;
    for(int i=1;i<=n;i++) s[i]=(s[i-1]+s[max(i-k-1,0)])%mod;

    cout<<s[n]<<endl;

    return 0;
}