solution-code4837

模板题，多注意细节即可

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

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

题目大意：快速地求

$ans = \frac{\sum_{i = 1}^{n} (i \cdot fib (i))}{\frac{n (n + 1)}{2}}$

\begin{aligned} ∵ \sum_{i = 1}^{n} fib (i) & = 1 + fib (1) + fib (2) + \dots + fib (n) - 1 [1 + (- 1) == 0] \\ = (fib (2) + fib (1)) + fib (3) + \dots + fib (n) - 1 [fib (1) == fib (2)] \\ = (fib (3) + fib (2)) + fib (4) + \dots + fib (n) - 1 [fib (1) + fib (2) == fib (3)] \\ = \dots \\ = fib (n + 2) - 1 \\ ∴ \sum_{i = 1}^{n} i \cdot fib (i) & = n \sum_{i = 1}^{n} fib (i) - \sum_{i = 1}^{n - 1} \sum_{j = 1}^{i} fib (j) \\ = n (fib (n + 2) - 1) - \sum_{i = 1}^{n - 1} (fib (i + 2) - 1) \\ = n \cdot fib (n + 2) - n - (\sum_{i = 1}^{n - 1} fib (i + 2)) + (n - 1) \\ = n \cdot fib (n + 2) - (\sum_{i = 1}^{n + 1} fib (i) - 2) - 1 \\ = n \cdot fib (n + 2) - (fib (n + 3) - 1 - 2) - 1 \\ = n \cdot fib (n + 2) - fib (n + 3) + 2 \end{aligned}

写一个矩阵快速幂就可以解决问题，时间复杂度 $O (T \cdot \log_{2} (n))$ ，但是不出意料的 T 掉了

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

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

[\begin{matrix} fib (n) \\ fib (n - 1) \end{matrix}] [\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}] = [\begin{matrix} fib (n - 1) \\ fib (n - 2) \end{matrix}]

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

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

最终的矩阵为：

[\begin{matrix} 1 \\ 0 \end{matrix}] {[\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}]}^{n + 3}

转载自 miskcoo

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

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

如果 $r (2 k + 1)$ 是个素数，那么在 $\mod r (2 k + 1)$ 意义下，可以处理 $2 k$ 以内规模的数据。

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

$1004535809 = 479 \times 2^{21} + 1$ 加起来刚好不会爆 int 也不错。

还有就是 UOJ 常用的 $998244353 = 119 \times 2^{23} + 1$ 。

打表方法：对于每个 $k$ ，找到最小 $r$ 满足 $r (2 k + 1)$ 是素数（ $g$ 是 $\mod r (2 k + 1)$ 的原根）。

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