矩阵快速幂+__int128 0分求助,悬赏一关注
查看原帖
矩阵快速幂+__int128 0分求助,悬赏一关注
546681
lcbridgeAK CSP-S楼主2023/8/22 20:29

RT,实在没看出哪错了

#include <bits/stdc++.h>
#define int __int128

using namespace std;

int m,a,c,x0,n,g;
struct matrix{
	int v[3][3],x,y;
};
void scan(__int128 &x){
    x=0;
	int f=1;
	char ch=getchar();
    while (!isdigit(ch)){if (ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    x*=f;
}
void _print(__int128 x){
    if(x>9)_print(x/10);
    putchar(x%10 + '0');
}
void print(__int128 x){
    if(x<0){
        x=-x;
        putchar('-');
    }
    _print(x);
}
matrix C,ANS;
void init(){
	memset(ANS.v,0,sizeof(ANS.v));
	ANS.x=1,ANS.y=2;
	ANS.v[1][1]=x0;
	ANS.v[1][2]=c;
	memset(C.v,0,sizeof(C.v));
	C.x=2,C.y=2;
	C.v[1][1]=a;
	C.v[1][2]=1;
	C.v[2][2]=1;
}
matrix mul(matrix A,matrix B){
	matrix R;
	memset(R.v,0,sizeof(R.v));
	R.x=A.x,R.y=B.y;
	for(int i=1;i<=A.x;i++){
		for(int j=1;j<=B.y;j++){
			for(int k=1;k<=A.y;k++){
				R.v[i][j]=(R.v[i][j]+A.v[i][k]*B.v[k][j])%m;
			}
		}
	}
	return R;
}
void qpow(int b){
	while(b){
		if(b&1)ANS=mul(ANS,C);
		C=mul(C,C);
		b>>=1;
	}
}
signed main(){
	scan(m),scan(a),scan(c),scan(x0),scan(n),scan(g);
	init();
	qpow(n-1);
	printf("%lld",ANS.v[1][1]%g);
	return 0;
}

谢谢!

2023/8/22 20:29
加载中...