和 lyh 想的差不多，我认为我写的会更详细一些。
dyc 好厉害。完全想不到这样的做法。
给你两个整数 \(n\)，\(m\)，让你求以下式子的值。
\[T(n) = \sum_{i=1}^{n} f(i)\times i\bmod m \]对于斐波那契数列 \(f(n)=f(n-1)+f(n-2)\) 这样的性质，使用前缀和化简式子是个好东西。
式子就变成了
\[T(n) = \sum_{i=1}^{n} s(n)-s(i-1) \]提出 \(s(n)\)，结合一下斐波那契数列的结论 \(s(i)=f(i+2)-1\)，进行代入。
\[T(n) = n\times s(n)-\sum_{i=1}^{n}s(i-1) \]对 \(\sum\) 进行化简
\[T(n) = n\times f(n+2)-n-\sum_{i=1}^{n} f(i+1) +n \]剩下的步骤很容易了。
\[\begin{aligned} T(n) &= n\times f(n+2)-n-\sum_{i=2}^{n+1} f(i)+n \\ &= n\times f(n+2)-n-\sum_{i=2}^{n+1}f(i)+f(1)-f(1)+n\\ &=n\times f(n+2)-n-\sum_{i=1}^{n+1}f(i) - f(1) +n\\ &=n\times f(n+2)-s(n+1)-1\\ &=n\times f(n+2)-(f(n+3)-1)-1\\ &=n\times f(n+2)-f(n+3)+2\\ \end{aligned}\]矩阵快速幂加速递推 \(f\) 即可，于是就用 \(\log\) 的优秀复杂度求 \(T(n)\) 了。
标签：化简,佳佳,sum,times,斐波,Fibonacci,式子 From： https://www.cnblogs.com/zxcqwq/p/18113581