鑫学长 AK 的烦恼
时间： 1ms 内存：256M
描述：
鑫学长最近参加了一场 Codeforces Div.2 的比赛，他在一道题中使用了如下的代码并取得了 Accept（其中 $0 \le n \le 20$，isprime 是一个判定素数的函数），没想到的是之后有一个更大数据范围的题目，这使鑫学长开始发愁了，因为他不知道该怎么优化下方的程序，你能帮他优化这个程序么，奖励嘛，当然是给你的 Accept 咯。
int solve(int n, int c) { if (n == 0) return 1; else if (n == 1) return 2; else if (isprime(n)) return c; return solve(n - 1, c) + solve(n - 2, c) + solve(n - 3, c); }由于增大数据范围以后所得到的结果也很大，因此你需要输出实际结果对 $1000000007$ 取模之后的数值。
输入：
输入两个整数 $n$ 与 $c$，其中 $0 \le n \le 10000, 0 \le c \le 100000$。
输出：
输出一个整数，它是样例程序中传入 $n$ 与 $c$ 所得到的结果对 $1000000007$ 取模之后的数值。（你需要优化样例程序）
示例输入：
3 5示例输出：
5提示：
参考答案（内存最优[1196]）：
#include<cstdio>
using namespace std;
const int mod=1e9+7;
int n,c;
int p[10005],f[10005];
int main()
{
scanf("%d%d",&n,&c);
p[0]=1;
p[1]=1;
for(int i=2;i<=n;i++)
{
if(p[i]==0)
for(int j=2*i;j<=n;j+=i)
p[j]=1;
}
f[0]=1;
f[1]=2;
for(int i=2;i<=n;i++)
{
if(p[i]==0)
f[i]=c;
else
f[i]=((f[i-1]+f[i-2])%mod+f[i-3])%mod;
}
printf("%d",f[n]);
}
参考答案（时间最优[3]）：
#include<cstdio>
using namespace std;
const int mod=1e9+7;
int n,c;
int p[10005],f[10005];
int main()
{
scanf("%d%d",&n,&c);
p[0]=1;
p[1]=1;
for(int i=2;i<=n;i++)
{
if(p[i]==0)
for(int j=2*i;j<=n;j+=i)
p[j]=1;
}
f[0]=1;
f[1]=2;
for(int i=2;i<=n;i++)
{
if(p[i]==0)
f[i]=c;
else
f[i]=((f[i-1]+f[i-2])%mod+f[i-3])%mod;
}
printf("%d",f[n]);
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。