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即可。
代码中高亮部分即为快速幂和快速乘法。
代码
#include <cstdio>
#include <cstring>
typedef unsigned long long lld;
lld mod;
inline lld qplus(lld x, lld y, lld mod){
lld t(x);
lld ans(0);
while (y > 0){
if (y % 2 == 1) ans = (ans + t) % mod;
t = (t + t) % mod;
y /= 2;
}
return ans;
}
class matrix{
public:
lld a[2][2];
matrix(){
memset(a, 0, sizeof(a));
}
friend matrix operator*(matrix x, matrix y){
matrix ans;
for (int i=0;i<=1;++i)
for (int k=0;k<=1;++k){
lld t=x.a[i][k];
for (int j=0;j<=1;++j)
ans.a[i][j] = (ans.a[i][j] + qplus(t, y.a[k][j], mod)) % mod;
}
return ans;
}
};
inline matrix power(matrix x, lld y){
matrix t=x;
matrix ans;
ans.a[0][0] = 1;
ans.a[1][1] = 1;
while (y > 0){
if (y % 2 == 1) ans = ans * t;
t = t * t;
y /= 2;
}
return ans;
}
lld m,a,c,x0,n,g;
int main(){
freopen("random.in", "r", stdin);
freopen("random.out", "w", stdout);
scanf("%lld%lld%lld%lld%lld%lld", &m, &a, &c, &x0, &n, &g);
matrix m1;
mod = m;
m1.a[0][0] = a % m;
m1.a[1][0] = c % m;
m1.a[1][1] = 1;
matrix ans;
matrix m2;
m2.a[0][0] = x0;
m2.a[0][1] = 1;
ans = power(m1, n);
ans = m2 * ans;
printf("%lld\n", ans.a[0][0] % g);
fclose(stdin);
fclose(stdout);
return 0;
}