前置知识：原根。对任意奇质数 p，一定存在原根 g（1<g<p）。g 满足：最小的使 g^e\equiv 1\pmod p 的正整数 e 为 p-1。g 有性质，g\bmod p,g^2\bmod p,\dots,g^{p-1}\bmod p 恰遍历 1,2,\dots,p-1各一次。
由于 n 为质数，不难发现题目所述变换 f 是可逆的。因此，所有可能的序列 a 构成若干等价类，每个等价类内恰有一个序列符合条件。
令一个序列 a 的权值为所在等价类的大小的倒数，则所求答案即为所有序列 a 的权值和。我们转而刻画权值。
继续寻找等价类的性质。注意到 f 变换不仅可逆，而且两个 f 变换的复合也可用一个 f 变换表示——本质上，f 是对下标的线性变换。这样，一个等价类内的两个序列，一定可以通过一次 f 变换互相转换。
考虑共有 n(n-1) 种不同的 f 变换。对于一个序列 a，若其中有 t 种变换相当于恒等变换（即，将 a 变换到 a），由于序列的对称性，a 所在的等价类内，所有序列均有 t 种恒等变换。结合「一个等价类内的两个序列，一定可以通过一次 f 变换互相转换」，可以推知，等价类大小为 \dfrac{n(n-1)}{t}。
若然，a 序列对答案的贡献为 \dfrac{t}{n(n-1)}。答案为
\sum_a\frac{t}{n(n-1)}=\frac{1}{{n(n-1)}}\sum_a t
需要计算所有序列 a 的恒等变换数之和。考虑「算两次」，计算一个变换 f 的贡献——有多少个序列 a，在 f 下变换导致恒等。
考虑变换 f(a,x,y)，将下标变换：i\to xi+y。序列 a 在对任意 i=0,1,\dots,n-1，a_i=a_{(xi+y)\bmod n} 时，才有 f(a,x,y)=a。若构建一个点编号 0,1,\dots,n-1 的图，连边 (i,xi+y)，则序列 a 的个数为 m^c，c 为图的连通块个数。
下求出 c。分类讨论：
考虑 f 将下标变换：i\to xi+y，若将序列旋转移位 \Delta（下标 i\to i+\Delta），则变换 f 的效果变为 i+\Delta\to xi+y+\Delta。令 x\Delta=y+\Delta，则变换相当于 i\to xi，等效于 y=0。这只需 \Delta=\frac{y}{x-1}，由于 x\neq 1 且 n 为质数，\Delta 在模 n 意义下存在。