P8377 [PFOI Round1] 暴龙的火锅

yc杨晨大家好 · 2022-06-06 12:20:26 · 题解

首先我们看到题目中有斐波那契数列，还有mod9明眼人都能看出来暴力会爆，那么又有什么方法呢？

我们先要知道一个定理：一个数的各位相加mod9就等于这个数mod9，所以显然易见答案就是斐波那契数列的1-n项加起来mod9，但斐波那契数列到后面显然也会爆，所以我们就将mod9融入斐波那契数列的计算中，毕竟mod9有万金油特性，改变顺序不会影响结果。

但这时我们又会发现时间会爆掉，所以就要引入前缀和做法，将数组预处理，直接输出结果。

代码如下：

t=int(input())
a=[0]*1000005
s=[0]*1000005
a[1]=a[2]=1
for i in range(3,1000003):
    a[i]=(a[i-1]+a[i-2])%9
for i in range(1,1000003):
    s[i]=s[i-1]+a[i]
while t:
    x=int(input())
    print(s[x]%9)
    t-=1