NOI2012 隨機數生成器
題意:
給定$x,y,n,a_{0},m,g$.
定義$a_{i}=x*a_{i-1}+y\ mod\ m$
求$a_{n}\ mod\ g$
$n,m,x,y,a<=10^{18},g<=10^{8}$
題解:
當n較小,可以直接算出$a_{n}$
可以得到$a_{n}$的通項公式 $a_{n}=x^{n}*a_{0}+y*\frac{x^{n-1}-1}{x-1}$
當m是素數時,可以通過求解逆元得到結果.
對于沒有特殊性質的數據該怎么做?
我們可以把遞推式構造成矩陣
$\begin{Bmatrix} a_{i} \\ y \end{Bmatrix} = \begin{Bmatrix} x & 1 \\ 0 & 1 \end{Bmatrix} * \begin{Bmatrix} a_{i-1} \\ y \end{Bmatrix} $
那就可以再$logn$內求出$a_{n}$
但是注意 $m$是LL范圍的,所以中間結果可能會溢出.
對于這種情況 可以使用"快速乘" 用快速冪的思路把乘法轉化成加法.這樣就可以實現LL乘法了.
#include<cstdio> #include<cstring> #include<iostream> using namespace std; #define ll long long ll n,m,g,x,y,a; void Add(ll &x,ll y){x+=y;if(x>=m)x-=m;} ll mul(ll a,ll b){ ll res=0; while(b){ if(b&1)Add(res,a); Add(a,a); b>>=1; } return res; } struct Mat{ int a,b; ll c[2][2]; Mat(){c[0][0]=c[0][1]=c[1][0]=c[1][1]=0;} Mat operator*(const Mat &tmp)const{ Mat t; for(int i=0;i<a;i++){ for(int j=0;j<tmp.b;j++) for(int k=0;k<b;k++) Add(t.c[i][j],mul(c[i][k],tmp.c[k][j])); } t.a=a,t.b=tmp.b; return t; } void init(int x,int y){ a=x,b=y; } }I; ll calc(){ ll b=n; Mat t;t.init(2,2); t.c[0][0]=x,t.c[0][1]=t.c[1][1]=1; I.init(2,1); I.c[0][0]=a; I.c[1][0]=y; while(b){ if(b&1)I=t*I; t=t*t; b>>=1; } return I.c[0][0]; } int main(){ // freopen("random.in","r",stdin); cin>>m>>x>>y>>a>>n>>g; x%=m,y%=m,a%=m; cout<<calc()%g<<endl; return 0; }
$By\ LIN452$
$2017.06.09$
浙公網安備 33010602011771號