C++(g++ 7.5.0) 解法, 执行用时: 4ms, 内存消耗: 1940K, 提交时间: 2023-04-01 15:41:36

#include <bits/extc++.h>
#define int long long
using namespace std;
constexpr int p = 5000011;
int a[100002],b[100003];
void solve() {
    int n,k;cin>>n>>k;
    a[1]=b[1]=1;
    for(int i=2;i<=n;++i)
       {
            a[i]=a[i-1]+b[i-1];
            if(i-k-1>0)(b[i]=b[i-k-1]+a[i-k-1])%=p;
        else b[i]=1;
        }
    cout<<(a[n]+b[n])%p;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    // std::cin >> t;
    for (; t--; solve());
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 760K, 提交时间: 2020-01-22 09:50:31

#include<cstdio>
using namespace std;
const int mod=5000011;
int f[100005],n,k;
int main()
{
	scanf("%d%d",&n,&k);
	f[0]=1;k++;
	for(int i=1;i<=n;i++)
	{
		f[i]=f[i-1];
		if(i<=k)f[i]++;
		else f[i]+=f[i-k];
		f[i]%=mod;
	}
	printf("%d",f[n]);
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 732K, 提交时间: 2019-09-14 08:27:39

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n, k;
	cin >> n >> k;
	vector <int> f(n + 1);
	auto F = [&] (int x) {return x < 1 ? 1 : f[x];};
	for (int i = 1; i <= n; ++i)
		f[i] = (F(i - 1) + F(i - k - 1)) % 5000011;
	cout << f[n];
}