@[XHY20180718](/user/399475) $f_i$ 是斐波那契第 $i$ 项
by Hot_tear @ 2024-02-27 18:41:42
@[青鸟_Blue_Bird](/user/234224) 假设 $f(1)=1,f(2)=1$，根据归纳，应该有
$$f(i)=f(i\bmod m)f(m-1)^{i/m}$$
矩阵快速幂即可。
by Adchory @ 2024-02-27 18:57:12
@[MoriyaSuwako](/user/590600) 你说得对，但是注意到你求的是 $\sum_{i=1}^n (f(i) \bmod f(m))$ 而不是 $(\sum_{i=1}^n f(i)) \bmod f(m)$ 所以你这一招应该不大行。
by Purslane @ 2024-02-27 19:02:28
@[Purslane_Ma](/user/120947) 额，式子应该是
$$f(i)\equiv f(i\bmod m)f(m-1)^{i/m}\pmod{f(m)}$$
枚举 $i/m$，算出 $n\bmod m$ 多余的贡献，这两个应该都能矩阵快速幂加速吧？
by Adchory @ 2024-02-27 19:09:49
@[MoriyaSuwako](/user/590600) 你说得对，但是你怎么对 $f(m)$ 取模。
by Purslane @ 2024-02-27 19:11:41
有道理，让我想想
by Adchory @ 2024-02-27 19:13:42
对不起我是弱智，你这个式子再加上斐波那契一大堆性质其实就可以做了。
注意到 $f(n+1) f(n-1) - f(n)^2 = (-1)^n$。
所以 $f(n-1)^2 + f(n-1) f(n) - f(n)^2 = (-1)^n$。
考虑对 $f(n)$ 取模，得到 $f^2(n-1) \equiv (-1)^n \pmod {f(n)}$。
事实上我们只需要求 $f(n+2) \bmod f(m)$。通过上面的式子很容易转化为 $f(n) \bmod f(m)$，其中 $n \le 2m$。
当 $n \le m$ 的时候非常好办。
否则转化为楼上的 $f(n-m) f(m-1) \bmod f(m)$。
后面我还没想好。
by Purslane @ 2024-02-27 19:15:25
@[Purslane_Ma](/user/120947) 请问dl这两个东西有什么区别咩？QAQ
by Hot_tear @ 2024-02-27 19:16:41
@[Purslane_Ma](/user/120947) 括号怎么添会有影响吗？/yun
by Hot_tear @ 2024-02-27 19:17:24
@[Hot_tear](/user/737112) 会吧。
就是 $((4+4) \bmod 7) \bmod 3 = 1$，但是 $((4 \bmod 7) + (4 \bmod 7)) \bmod 3 = 2$。
by Purslane @ 2024-02-27 19:27:02