模板题，多注意细节即可

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

题目大意：快速地求

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

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

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

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

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

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

最终的矩阵为：

转载自 miskcoo

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

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

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

$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(2k+1)$ 是素数（$g$ 是 $\mathrm{mod}r(2k+1)$ 的原根）。

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