https://www.lydsy.com/JudgeOnline/problem.php?id=2875
https://www.luogu.org/problemnew/show/P2044
被带偏了想找循环节结果发现是m的……mmp。
实际上可以直接用矩阵乘法来表达。
|a c| |xn| |xn+1|
|0 1| |1 | |1 |
恩没了。
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
inline ll read(){
ll X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
ll n,p,a,c,x0;
int g;
inline ll multi(ll x,ll y){
ll res=;
while(y){
if(y&)(res+=x)%=p;
(x+=x)%=p;y>>=;
}
return res;
}
struct matrix{
ll g[][];
matrix(){
memset(g,,sizeof(g));
}
matrix operator *(const matrix &b)const{
matrix c;
for(int i=;i<;i++)
for(int j=;j<;j++)
for(int k=;k<;k++)
(c.g[i][j]+=multi(g[i][k],b.g[k][j]))%=p;
return c;
}
};
inline matrix qpow(matrix x,ll y){
matrix res;
res.g[][]=res.g[][]=;
while(y){
if(y&)res=res*x;
x=x*x;y>>=;
}
return res;
}
int main(){
p=read(),a=read(),c=read(),x0=read(),n=read(),g=read();
matrix A,B;
A.g[][]=a;A.g[][]=c;A.g[][]=;B.g[][]=x0;B.g[][]=;
A=qpow(A,n);B=A*B;
printf("%lld\n",B.g[][]%g);
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++