『做题记录』Test 8.22

压轴题 Hard

题面

求所有长度为 $p$ 的非负整数序列 $f$ ( 下标从 0 开始 ) . $\forall x \in [0 , p - 1]$ : $f_{k x \mod p} = k f_x \mod p$ 的方案总数 .

解题思路

$k = 0$ 或 $k = 1$ 时特判 .

费马小定理得到该等式构成若干个环 , $f_0$ 始终为 0 . 暴力找环即可 .

复杂度 $O(p)$ .