鑫学长 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]);
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。