「AT1733」「Xmas Contest 2015」Accumulation
题意
1 | input n |
求 \(\sum\limits_{i=1}^{n} s_i\) 的值（不需要对 \(c\) 取模）。
\(n\le 10^6, t\le 10^9,0\le x,a,b< c\le 10^9\)
题解
考虑快速进行 for j = 1 .. t : x = (a * x + b) mod c 这段操作。
\[\begin{aligned} j=1: &\quad ax+b \\ j=2: &\quad a(ax+b)+b=a^2x+ab+b \\ j=3: & \quad a(a^2x+ab+b)+b=a^3x+a^2b+ab+b \\ j=4: & \quad a^4x+a^3b+a^2b+ab+b\\ \vdots& \\ j=t:&\quad a^tx+\sum_{k=0}^{t-1} a^kb=a^tx+b\sum_{k=0}^{t-1}a^k\end{aligned}\]
如果 \(c\) 为质数，则这个式子可以直接用快速幂和等比数列求和公式进行计算。然而并没有保证 \(c\) 是质数，怎么办呢？可以发现，\(x\) 和 \(b\) 在这个式子中是常数，而 \(a^t\) 和 \(\sum\limits_{k=0}^{t-1}a^k\) 有某种联系……
考虑用矩阵表示（记 \(f(t)=\sum\limits_{k=0}^{t-1}a^k\)） \[A=\begin{bmatrix} a^t & f(t) \end{bmatrix},B=\begin{bmatrix} a^{t+1} & f(t+1) \end{bmatrix}\]
\(A\) 如何才能转化为 \(B\)，通过计算发现：\(a^{t+1}=a\cdot a^t,f(t+1)=a^t+f(t)\)，那么很显然转移矩阵为 \[C=\begin{bmatrix} a & 1\\ 0 & 1\end{bmatrix}\]
可以再验证一下 \(A\times C=B\)。于是直接用矩阵快速幂进行优化即可。
可以发现，最后 \(x\) 的转移一定可以表示为 \(px+q\) 的形式，所以只要一开始预处理 \(p,q\)，不需要每次进行矩阵快速幂。
时间复杂度 \(O(n+\log t)\)。
代码
1 |
|
upd: 修复了代码中的一个漏洞
