FBRICK - Xếp hình
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
long long base;
struct matrix
{
long long a[6][6];
void load(int x)
{
x%=base;
a[0][0]=a[1][2]=a[2][0]=a[2][1]=a[4][5]=1;
a[3][3]=a[5][4]=base-1;
a[3][0]=-4LL*x;
while (a[3][0]<0) a[3][0]+=base;
a[3][1]=a[3][0];
a[1][0]=a[1][1]=4LL*x*x%base;
a[1][3]=a[4][4]=2LL*x%base;
}
void multiply(matrix x,matrix y)
{
memset(a,0,sizeof(a));
for (int i=0;i<6;i++)
for (int j=0;j<6;j++)
for (int k=0;k<6;k++) a[i][j]=(a[i][j]+x.a[i][k]*y.a[k][j])%base;
}
};
matrix m[33],u;
long long ans[6];
void multi(long long a[],matrix m)
{
long long b[6]={0};
for (int j=0;j<6;j++)
for (int i=0;i<6;i++)
b[j]=(b[j]+a[i]*m.a[i][j])%base;
for (int i=0;i<6;i++) a[i]=b[i];
};
int main()
{
int test,x,n,i;
cin >> test;
while (test--)
{
cin >> x >> n >> base;
if (base==1)
{
puts("0"); continue;
}
n-=2;
m[0].load(x);
for (i=1;1<<i<=n;i++) m[i].multiply(m[i-1],m[i-1]);
ans[1]=1LL*x*x%base; ans[0]=ans[1]+1;
ans[3]=ans[4]=x%base; ans[2]=ans[5]=1;
while (n)
{
--i;
if (1<<i<=n) n-=1<<i, multi(ans,m[i]);
}
cout << ans[0] << endl;
}
}