BZOJ3328 PYXFIB 题解

好像网上没有这么做的题解，所以就写个吧。

直接单位根反演，就有： $$\frac{1}{k}\sum _{j=0}^{k-1}\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})({\omega }_k^j{)}^i{F}_i$$ 正常的做法是把斐波那契数用矩阵表示，然后用二项式定理。

考虑直接头铁用通项公式展开斐波那契数，就有 $$\frac{1}{\sqrt{5}k}\sum _{j=0}^{k-1}(\frac{1+\sqrt{5}}{2}(1+\frac{1+\sqrt{5}}{2}{\omega }_k^j{)}^n-\frac{1-\sqrt{5}}{2}(1+\frac{1-\sqrt{5}}{2}{\omega }_k^j{)}^n)$$ 在模意义下可能没有 $5$ 的二次剩余，故考虑扩域，把数表示成 $a+b\sqrt{5}$ 的形式。

定义一下扩域后数的加减乘除然后直接做即可。在这里除法的本质是求逆元，也就是求 $c+d\sqrt{5}$ 使得它和 $a+b\sqrt{5}$ 乘起来为 $1$。

不过需要注意的是，当 $P=5$ 的时候，$\frac{1}{\sqrt{5}k}$ 没有逆元，这样就会 WA，考虑特殊处理一下。

可以发现 $\frac{1}{\sqrt{5}k}$ 表示成 $a+b\sqrt{5}$ 的形式的时候 $a=0$，那么当 $P\ne 5$ 的时候它的逆元 $a=0$，既然这样，后面的式子求出来的 $a$ 也会等于 $0$。

所以我们根本没有必要在这一步把这个复数求逆，直接把 $k$ 求逆乘上后面的式子求出来的 $b$ 即可。

常数可能会比矩阵乘法的做法小。