solution-code4837

模板题，多注意细节即可

[luogu4834]萨塔尼亚的期末考试

这里有 oeis 的解释，但是我看不懂。

题目大意：快速地求

$a n s = \sum 𝑛 𝑖 = 1 (𝑖 \cdot f i b (𝑖)) 𝑛 (𝑛 + 1) 2$

∵ 𝑛 \sum 𝑖 = 1 f i b (𝑖) = 1 + f i b (1) + f i b (2) + \dots + f i b (𝑛) - 1 [1 + (- 1) = = 0] = (f i b (2) + f i b (1)) + f i b (3) + \dots + f i b (𝑛) - 1 [f i b (1) = = f i b (2)] = (f i b (3) + f i b (2)) + f i b (4) + \dots + f i b (𝑛) - 1 [f i b (1) + f i b (2) = = f i b (3)] = \dots = f i b (𝑛 + 2) - 1 ∴ 𝑛 \sum 𝑖 = 1 𝑖 \cdot f i b (𝑖) = 𝑛 𝑛 \sum 𝑖 = 1 f i b (𝑖) - 𝑛 - 1 \sum 𝑖 = 1 𝑖 \sum 𝑗 = 1 f i b (𝑗) = 𝑛 (f i b (𝑛 + 2) - 1) - 𝑛 - 1 \sum 𝑖 = 1 (f i b (𝑖 + 2) - 1) = 𝑛 \cdot f i b (𝑛 + 2) - 𝑛 - (𝑛 - 1 \sum 𝑖 = 1 f i b (𝑖 + 2)) + (𝑛 - 1) = 𝑛 \cdot f i b (𝑛 + 2) - (𝑛 + 1 \sum 𝑖 = 1 f i b (𝑖) - 2) - 1 = 𝑛 \cdot f i b (𝑛 + 2) - (f i b (𝑛 + 3) - 1 - 2) - 1 = 𝑛 \cdot f i b (𝑛 + 2) - f i b (𝑛 + 3) + 2

写一个矩阵快速幂就可以解决问题，时间复杂度 $𝑂 (𝑇 \cdot l o g 2 (𝑛))$ ，但是不出意料的 T 掉了

观察一下结果，可以发现我们分别对 ans 中两个相邻的 fib 值进行计算，这并没有利用好矩阵乘法的性质

回想一下最初学习矩阵快速幂的时候，老师演算 fib 的时候是一个 $1 \times 2$ 的矩阵乘上 $2 \times 2$ 的矩阵，像这样：

[f i b (𝑛) f i b (𝑛 - 1)] [1110] = [f i b (𝑛 - 1) f i b (𝑛 - 2)]

我们用老师最初讲的方法来计算 fib 的值，可以节省一半的时间，在加上 $2 \times 2$ 的矩阵乘法不用 for 循环，就可以轻松切过这道题了～

UPD: 老师最后写的方法并不是错的，在只求一次或者不相邻的项中会显得更快一些，但这并不代表我们可以忘掉原来讲的那种方法（这真的是一道好题）

最终的矩阵为：

[10] [1110] 𝑛 + 3

转载自 miskcoo

是这样的，这几天在写 NTT，由于是在模意义下的，需要各种素数……

然后就打了个表方便以后查了。

如果 $𝑟 (2 𝑘 + 1)$ 是个素数，那么在 $m o d 𝑟 (2 𝑘 + 1)$ 意义下，可以处理 $2 𝑘$ 以内规模的数据。

$2281701377 = 17 \times 227 + 1$ 是一个挺好的数，平方刚好不会爆 long long。

$1004535809 = 479 \times 221 + 1$ 加起来刚好不会爆 int 也不错。

还有就是 UOJ 常用的 $998244353 = 119 \times 223 + 1$ 。

打表方法：对于每个 $𝑘$ ，找到最小 $𝑟$ 满足 $𝑟 (2 𝑘 + 1)$ 是素数（ $𝑔$ 是 $m o d 𝑟 (2 𝑘 + 1)$ 的原根）。

一场简单题之战，就是比做题的速度以及正确率（感觉出题人去看球赛去了）