蝴蝶翅膀的发散

C(clang11) 解法, 执行用时: 15ms, 内存消耗: 504K, 提交时间: 2020-12-26 16:26:13

#include <stdio.h>

int main()
{
	int n,d;
	scanf("%d%d",&n,&d);
	long long a[10010]={0,1,1},b[10010]={0,1};
	int i;
	for(i=3;i<=n;i++){
		int max=(i-d>1)?i-d:1;
		for(int j=max;j<=i-1;j++)
		  b[i]+=a[j]%1000000007;
		a[i]=b[i];
	}
	printf("%d",(b[n]+1000000007)%1000000007);
	return 0;
}

C++(clang++11) 解法, 执行用时: 40ms, 内存消耗: 528K, 提交时间: 2021-01-22 15:04:22

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll f[10010];
const int p=1e9+7;
int main()
{
	int n,d;
	scanf("%d%d",&n,&d);
	f[1]=1;
	for(int i=2;i<=n;i++)
	{
		int k=max(i-d,1);
		for(int j=k;j<=i-1;j++)
		f[i]+=f[j],f[i]%=p;
	}
	cout<<f[n];
}

Python3(3.9) 解法, 执行用时: 40ms, 内存消耗: 16760K, 提交时间: 2020-12-26 12:28:17

a = [0] * 10007
pre = [0] * 10007
MOD = 10**9 + 7

n, d = map(int, input().split())
a[1] = pre[1] = 1

for i in range(2, n + 1):
    l, r = max(i - d, 1), i - 1
    a[i] = pre[r] - pre[l - 1]
    pre[i] = a[i] + pre[i - 1]

print(a[n] % MOD)

详情