FBRICK - Xếp hình
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
typedef long long ll;
struct matrix {
int m,n;
ll d[10][10];
};
int n;
ll a2;
ll mod;
matrix fst,mul;
matrix multi(const matrix &a,const matrix &b) {
int i,j,k;
int x=a.m;
int y=a.n;
int z=b.n;
matrix c;
c.m=x;c.n=z;
for (i=0;i<x;i=i+1)
for (j=0;j<z;j=j+1) {
c.d[i][j]=0;
for (k=0;k<y;k=k+1)
c.d[i][j]=(c.d[i][j]+a.d[i][k]*b.d[k][j])%mod;
}
return (c);
}
matrix multiply(const matrix &a,const int &k) {
if (k==1) return (a);
matrix r=multiply(a,k/2);
r=multi(r,r);
if (k%2==1) r=multi(r,a);
return (r);
}
void process(void) {
scanf("%lld",&a2);
scanf("%d",&n);
scanf("%lld",&mod);
if (mod==1) {
printf("0\n");
return;
}
mul.m=4;
mul.n=4;
mul.d[0][0]=1;
mul.d[0][1]=0;
mul.d[0][2]=0;
mul.d[0][3]=0;
mul.d[1][0]=(4*a2*a2)%mod;
mul.d[1][1]=(4*a2*a2)%mod;
mul.d[1][2]=1;
mul.d[1][3]=(2*a2)%mod;
mul.d[2][0]=1;
mul.d[2][1]=1;
mul.d[2][2]=0;
mul.d[2][3]=0;
mul.d[3][0]=(-4*a2)%mod+mod;
mul.d[3][1]=(-4*a2)%mod+mod;
mul.d[3][2]=0;
mul.d[3][3]=mod-1;
fst.m=1;
fst.n=4;
fst.d[0][0]=(1+a2*a2)%mod;
fst.d[0][1]=(a2*a2)%mod;
fst.d[0][2]=1;
fst.d[0][3]=a2%mod;
if (n>2) fst=multi(fst,multiply(mul,n-2));
if (fst.d[0][0]<0) fst.d[0][0]+=mod;
printf("%lld\n",fst.d[0][0]);
}
int main(void) {
int t,c;
scanf("%d",&t);
for (c=1;c<=t;c=c+1) process();
return 0;
}