來自FallDream的博客，未經(jīng)允許，請(qǐng)勿轉(zhuǎn)載，謝謝。

---

棟棟最近迷上了隨機(jī)算法，而隨機(jī)數(shù)是生成隨機(jī)算法的基礎(chǔ)。棟棟準(zhǔn)備使用線性同余法（Linear Congruential Method）來生成一個(gè)隨機(jī)數(shù)列，這種方法需要設(shè)置四個(gè)非負(fù)整數(shù)參數(shù)m,a,c,X[0],按照下面的公式生成出一系列隨機(jī)

數(shù)X[n]X[n+1]=(aX[n]+c)mod m其中mod m表示前面的數(shù)除以m的余數(shù)。從這個(gè)式子可以看出，這個(gè)序列的下一個(gè)數(shù)總是由上一個(gè)數(shù)生成的。用這種方法生成的序列具有隨機(jī)序列的性質(zhì)，因此這種方法被廣泛地使用，包括常用的C++和Pascal的產(chǎn)生隨機(jī)數(shù)的庫函數(shù)使用的也是這種方法。棟棟知道這樣產(chǎn)生的序列具有良好的隨機(jī)性，不過心急的他仍然想盡快知道X[n]是多少。由于棟棟需要的隨機(jī)數(shù)是0,1,...,g-1之間的，他需要將X[n]除以g取余得到他想 的數(shù)，即X[n] mod g，你只需要告訴棟棟他想要的數(shù)X[n] mod g是多少就可以了。? n,m,a,c,X[0]<=10^18 很容易構(gòu)造轉(zhuǎn)移矩陣 [a][c]?? ????? [xn]????->? [xn+1]?? [0][1]??? *? ?[1]???? ->?????[1] 然后發(fā)現(xiàn)數(shù)字太大，所以寫一個(gè)大整數(shù)乘法就行了。 #include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; inline ll read() {ll x = 0 , f = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f; } ll mod,a,c,x,n,g; ll mul(ll X,ll Y) {ll sum=0;for(ll Z=Y;X;X>>=1,Z=(Z<<1)%mod) if(X&1) sum=(sum+Z)%mod;return sum; } struct Matrix {ll s[3][3],r,c;Matrix(int x=0,int y=0){r=x;c=y;memset(s,0,sizeof(s));}Matrix operator*(Matrix b){Matrix d(r,b.c);for(int i=1;i<=r;i++)for(int k=1;k<=c;k++)for(int j=1;j<=b.c;j++)d.s[i][j]=(d.s[i][j]+mul(s[i][k],b.s[k][j]))%mod;return d; } }A(2,2),B(2,1);main() {mod=read();a=read();c=read();x=read();n=read();g=read();A.s[1][1]=a;A.s[1][2]=c;A.s[2][2]=1;B.s[2][1]=1;B.s[1][1]=x;for(;n;n>>=1,A=A*A) if(n&1) B=A*B;printf("%lld\n",B.s[1][1]%g); return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/FallDream/p/bzoj2875.html

總結(jié)

以上是生活随笔為你收集整理的[bzoj2875][Noi2012]随机数生成器的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。