[NOI2012] 随机数生成器
题目描述
栋栋最近迷上了随机算法,而随机数是生成随机算法的基础。栋栋准备使用线性同余法(Linear Congruential Method)来生成一个随机数列,这种方法需要设置四个非负整数参数 $m,a,c,X_0$,按照下面的公式生成出一系列随机数 $\{X_n\}$: $$X_{n+1}=(aX_n +c)\bmod m$$ 其中 $\bmod m$ 表示前面的数除以 $m$ 的余数。从这个式子可以看出,这个序列的下一个数总是由上一个数生成的。 用这种方法生成的序列具有随机序列的性质,因此这种方法被广泛地使用,包括常用的 C++ 和 Pascal 的产生随机数的库函数使用的也是这种方法。 栋栋知道这样产生的序列具有良好的随机性,不过心急的他仍然想尽快知道 $X_n$ 是多少。由于栋栋需要的随机数是 $0,1,\dots,g-1$ 之间的,他需要将 $X_n$ 除以 $g$ 取余得到他想要的数,即 $X_n \bmod g$,你只需要告诉栋栋他想要的数 $X_n \bmod g$ 是多少就可以了。
输入输出格式
输入格式
一行 $6$ 个用空格分割的整数 $m,a,c,X_0,n$ 和 $g$,其中 $a,c,X_0$ 是非负整数,$m,n,g$ 是正整数。
输出格式
输出一个数,即 $X_n \bmod g$。
输入输出样例
输入样例 #1
11 8 7 1 5 3
输出样例 #1
2
说明
计算得 $X_n=X_5=8$,故$(X_n \bmod g) = (8 \bmod 3) = 2$。 对于 $100\%$ 的数据,$n,m,a,c,X_0\leq 10^{18}$,$1\leq g\leq 10^8$,$n,m\geq 1$,$a,c,X_0\geq 0$。
矩阵乘法模板题
由递推公式$X_{n+1}=(aX_n +c)\bmod m$
构造两矩阵
$$E_0 = \begin{Bmatrix}X_0 &c\end{Bmatrix}$$
$$V = \begin{Bmatrix}
a & 0\\
1 & 1
\end{Bmatrix}$$
$$E_0 * V^{n} = E_n = \begin{Bmatrix}X_n &c\end{Bmatrix}$$
直接上矩阵快速幂
注意乘积会爆 $long long$ 要用龟速乘
#include <bits/stdc++.h>
using namespace std;
long long m, a, c, X0, n, g;
long long calc(long long x,long long y)
{
long long res = 0;
while(y)
{
if(y & 1) res = (res + x) % m;
x = (x + x) % m;
y >>= 1;
}
return res;
}
struct Martix
{
long long f[4][4];
void clear()
{
memset(f, 0, sizeof f);
}
Martix operator*(const Martix b)
{
Martix c;
c.clear();
for(int i = 1; i <= 2; i++)
{
for(int j = 1; j <= 2; j++)
{
for(int k = 1; k <= 2; k++)
{
c.f[i][j] += calc(f[i][k] , b.f[k][j]);
c.f[i][j] %= m;
}
}
}
return c;
}
};
Martix E, V;
Martix qp(Martix a, long long b)
{
Martix res = V;
b--;
while(b)
{
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
int main()
{
cin >> m >> a >> c >> X0 >> n >> g;
E.clear(); V.clear();
E.f[1][1] = X0; E.f[1][2] = c;
V.f[1][1] = a; V.f[1][2] = 0;
V.f[2][1] = 1; V.f[2][2] = 1;
E = E * qp(V, n);
cout << E.f[1][1] % g;
return 0;
}