首页 > 代码库 > codevs1281 Xn数列

codevs1281 Xn数列

2024-08-11 21:57:52   223人阅读

题目描述 Description

给你6个数，m, a, c, x0, n, g

Xn+1 = ( aXn + c ) mod m，求Xn

m, a, c, x0, n, g<=10^18

输入描述 Input Description

一行六个数 m, a, c, x0, n, g

输出描述 Output Description

输出一个数 Xn mod g

样例输入 Sample Input

11 8 7 1 5 3

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

int64按位相乘可以不要用高精度。

 

 

正解：矩阵快速幂+矩阵乘法

解题报告：

　　对于一个递推式，求某一项的值。

　　这显然是可以矩阵乘法的，用一下快速幂就可以了。但是注意一点，因为对于long long下的乘法很有可能会乘炸，所以我们需要用加法模拟一下乘法（快速幂的形式），就可以啦。

　　代码如下：　　

　　

 1 //It is made by jump~ 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <ctime> 9 #include <vector>10 #include <queue>11 #include <map>12 #include <set>13 using namespace std;14 typedef long long LL;15 LL MOD,A,C,n,g;16 struct matrix{17     LL a[2][2];18 }ans,init;19 20 inline LL getlong()21 {22        LL w=0,q=0; char c=getchar();23        while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar(); if(c==‘-‘) q=1,c=getchar(); 24        while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar(); return q ? -w : w;25 }26 27 inline LL quick_cj(LL x,LL y){//为防止溢出，用快速幂的方法，用加法代替乘法28     LL da=0;29     while(y>0) {30     if(y&1) da+=x,da%=MOD;31     x+=x; x%=MOD;32     y>>=1;33     }34     return da;35 }36 37 inline matrix cj(matrix a,matrix b){38     matrix c=init;39     for(int i=0;i<2;i++)40     for(int j=0;j<2;j++)41         for(int k=0;k<2;k++)42         c.a[i][j]+=quick_cj(a.a[i][k],b.a[k][j]),c.a[i][j]%=MOD;43     return c;44 }45 46 inline matrix mul(LL x){47     matrix base,tmp; tmp=base=init;48     tmp.a[0][0]=1; tmp.a[1][1]=1;49     base.a[0][0]=A; base.a[0][1]=0;50     base.a[1][0]=base.a[1][1]=1;51     while(x>0) {52     if(x&1) tmp=cj(tmp,base);53     base=cj(base,base);54     x>>=1;55     }56     return tmp;57 }58 59 inline void work(){60     MOD=getlong(); A=getlong(); C=getlong(); 61     ans.a[0][0]=getlong(); ans.a[0][1]=C; n=getlong(); g=getlong();    62     for(int i=0;i<2;i++) for(int j=0;j<2;j++) init.a[i][j]=0;63     ans=cj(ans,mul(n));64     printf("%lld",ans.a[0][0]%g);65 }66 67 int main()68 {69   work();70   return 0;71 }

 

codevs1281 Xn数列


联系
我们