题目描述: 这次的问题和上个题目《Py的函数I》相同,不过现在要求的n很大(0 <= n <= 1000000000). 请你输出F(n)取模20132013之后的值。
示例: 输入: n = 0 输出: 1
分析: 对于这个题目,和上个题目一样,就是数据量上来了,原本的算法时间肯定超时了,但是我还是不死心,提交了一下,然后果然超时了。
我就在想,这个可不可能会循环起来? 为什么我会这么去想,因为最后的结果是要对 20132013 取模的,那么最后也就是只有 20132013 个不同的数。所以我猜,它有可能循环。 于是我 写了一个代码,把所有的结果保存下来,然后看看到什么位置会循环。于是被我发现了 n = 7019640 开始循环。于是事情就简单了。
代码:
1
2
3
4
5
6
7
8
9
10
n = n % 7019640
def main(n):
ans = [1, 3, 0]
for i in range(2, n+1):
r = (3 * ans[(i-1)%3] + 2 * ans[(i-2)%3] + 1) % 20132013
ans[i%3] = r
print(ans[n%3])
main(n)