初赛
Q
不是 wr 没救了，题目是这样
\[\begin{cases}x_1=p \\ x_{i + 1} = ax_i - a\end{cases}
\]
求 \(a_n \bmod c,n \leq 10^9\)。
你作为一个人类 肯定会思考特征根、生成函数、矩快 对吧，
然后 wr 给我说你要转化成 \(k\) 进制，直观的体验一下这个过程：
\[(33)_4 \rightarrow (320)_4 \rightarrow (3130)_4\rightarrow (31230)_4 \rightarrow (312230)_4
\]
发现每个 \(-1\) 操作都只会修改当前项的最后一位，而除了 \(x_1\) 之外每一项的最后一位都是 \(0\)，除了 \(x_1,x_2\) 以外每一项的倒数第二位位都是 \(n - 1\)，之后会依次添加 \(n - 2\)。
所以答案是
\[x_n=[x_2-(a-1)a]a^{n - 2}+(a-2)(a^2+a^3+\cdots+a^{n-1})+(a-1)a
\]
只要递归处理等比数列求求和暴力跑 \(n \leq 5\) 的 corner case 就好了。