内容简介:栋栋最近迷上了随机算法,而随机数是生成随机算法的基础。栋栋准备使用线性同余法(Linear Congruential Method)来生成一个随机数列,这种方法需要设置四个非负整数参数\[X_{n+1}=(aX_n +c)\bmod m \]其中
NOI2012 随机数生成器
题目描述
栋栋最近迷上了随机算法,而随机数是生成随机算法的基础。栋栋准备使用线性同余法(Linear Congruential Method)来生成一个随机数列,这种方法需要设置四个非负整数参数 \(m,a,c,X_0\) ,按照下面的公式生成出一系列随机数 \(\{X_n\}\) :
\[X_{n+1}=(aX_n +c)\bmod m \]
其中 \(mod\ m\) 表示前面的数除以 \(m\) 的余数。从这个式子可以看出,这个序列的下一个数总是由上一个数生成的。
栋栋知道这样产生的序列具有良好的随机性,不过心急的他仍然想尽快知道 \(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\) 。
输入输出样例
输入
输出
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\) 。
题意
给出了一个迷惑式子,让你算出来式子的第 \(n\) 项,然后 \(mod\ g\) 的结果
分析
看到这样一个个的递推式子,一个个用 \(for\) 循环来推肯定不行,所以很容易就会想到要用到矩阵快速幂来求。那么我们现在的主要任务就是构造矩阵来进行乘法运算。
首先看到题目中给出的式子:
\[X_{n+1}=(aX_n+c)\ mod\ m \]
取模运算可以暂且先不看,因为对结果没什么影响,在矩阵乘法的时候进行取模就行了。所以转化成如下式子:
\[X_{n+1}=aX_n+c \]
那么我们就可以根据这个式子来构造矩阵。由矩阵的乘法运算为结果矩阵的 \(i\) 行 \(j\) 列为前边矩阵一个的第 \(i\) 行乘以另一个的第 \(j\) 列,所以我们可以得出如下的矩阵递推式子:
\[\left[ \begin{matrix} X_{n-1}\\ c \end{matrix} \right]\times \left[ \begin{matrix} a & 1\\ 0 & 1 \end{matrix} \right] = \left[ \begin{matrix} X_{n}\\ c \end{matrix} \right] \]
这里用 \(X_{n-1}\) 这一列分别乘以右边矩阵的第一第二行,得到结果的矩阵,那么我们就可以根据这个递推式子来进行矩阵快速幂。
这里乘法的运算过程如下:
\[X_{n-1}\times a+c\times 1 = X_n \]
\[X_{n-1}\times 0+c\times 1 = c \]
由此得到结果矩阵
这里的矩阵做乘法的时候需要用到龟速乘,不然会爆 \(long\ long\)
代码
#include<bits/stdc++.h> using namespace std; #define int long long struct Node{//矩阵结构体 int a[5][5]; }; int m,a,c,x0,g,n; int ksj(int a,int b){//龟速乘 int ans = 0; while(b){ if(b & 1)ans = (ans + a) % m; a = (a + a) % m; b >>= 1; } return ans; } Node Mul(Node a,Node b,int c){//矩阵乘法,记得取模 Node ans; memset(ans.a,0,sizeof(ans.a)); for(int i=1;i<=2;++i){ for(int j=1;j<=2;++j){ for(int k=1;k<=2;++k){ ans.a[i][j] = (ans.a[i][j] + ksj(a.a[i][k],b.a[k][j])%c)%c; } } } return ans; } Node ans; void qpow(Node &ans,Node b,int c){//矩阵快速幂 while(c){ if(c & 1)ans = Mul(b,ans,m); b = Mul(b,b,m); c >>= 1; } } signed main(){ Node bas; scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&x0,&n,&g); ans.a[1][1] = x0;//初始化矩阵 ans.a[2][1] = c; bas.a[1][1] = a; bas.a[1][2] = 1; bas.a[2][1] = 0; bas.a[2][2] = 1; qpow(ans,bas,n); printf("%lld\n",ans.a[1][1] % g);//得答案 }
以上所述就是小编给大家介绍的《[NOI2012]随机数生成器【矩阵快速幂】》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- [洛谷P3600]随机数生成器
- 区块链随机数的实现:墨客随机数子链RandDrop(强随机数和真随机数)_作者陈小虎
- Java随机数探秘
- Java 随机数探秘
- php里的随机数
- [译] 随机数与区块链
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。