鑫学长 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
提示:
参考答案:
文章评论