题解
水矩乘。
唯一要注意的是爆炸的乘法运算。
快速乘解决即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
using namespace std;
typedef long long ll;
typedef struct{
ll dat[3][3];
int r,c;
}Mat;
ll M,A,C,x0,n,G;
Mat mid,tmp;
ll mulll(ll a,ll b){
ll res=0;
while(b){
if(b&1)res=(res+a)%M;
a=(a+a)%M;b>>=1;
}
return res;
}
void mul(Mat &a,Mat &b,Mat *to){
to->r=a.r,to->c=b.c;
int i,j,k;ll t;
for(i=0;i<a.r;i++)
for(j=0;j<b.c;j++){
t=0;for(k=0;k<a.c;k++)t+=mulll(a.dat[i][k],b.dat[k][j]),t%=M;
to->dat[i][j]=t%M;
}
}Mat pow(Mat a,ll p){
Mat E,F;
E.r=E.c=a.c;
int i,j;
for(i=0;i<a.c;i++)
for(j=0;j<a.c;j++)
E.dat[i][j]=(i==j)?1:0;
while(p){
if(p&1)mul(E,a,&F),E=F;
mul(a,a,&F),a=F;p>>=1;
}return E;
}
int main(){
scanf("%lld%lld%lld%lld%lld%lld",&M,&A,&C,&x0,&n,&G);
Mat fib,d,u,v;
fib.r=fib.c=2;
fib.dat[0][0]=A%M;
fib.dat[0][1]=fib.dat[1][1]=1;
fib.dat[1][0]=0;
u=pow(fib,n);
d.r=2,d.c=1;
d.dat[0][0]=x0%M,d.dat[1][0]=C%M;
mul(u,d,&v);
printf("%lld\n",v.dat[0][0]%G);
return 0;
}