bzoj2845,noi2012随机数生成器解题报告

 题意

给出\(m,a,c,x_0,n, g\)  \(  x_{n+1}=(a\times x_n+c)\%m\),求\(x_n % g\)

算法分析

该题可利用矩阵倍增来实现。利用矩阵乘法和矩阵乘法的结合律,有如下性质:

\[
\begin{bmatrix}
a_{n-1} & 1
\end{bmatrix}
\times
\begin{bmatrix}
a & 0\\
c & 1
\end{bmatrix}
=
\begin{bmatrix}
a_n & 1
\end{bmatrix}
\]

那么就有:

\[
\begin{bmatrix}
a_{0} & 1
\end{bmatrix}
\times
{\begin{bmatrix}
a & 0\\
c & 1
\end{bmatrix}}^n
=
\begin{bmatrix}
a_n & 1
\end{bmatrix}
\]

由于n较大,我们可以对矩阵进行快速幂,方法如下:

将n分解为2进制的形式,设置一个临时变量t,初值为x矩阵。

循环n的2进制位数这么多次,每次判断n的第i位是否为一,若为1,则ans=ans*t。最后t=t*t。

此外,该题会有两个long long相乘,会溢出。需进行快速乘法。方法同上,把t=t*t改为t=t*2,把ans=ans*t改为ans = ans + t即可。

代码中高亮部分即为快速幂和快速乘法。

代码