FBRICK - Xếp hình
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<cstring>
const long long base[4][4] = {{1,0,0,0},{0,1,0,0},{0,0,1,0},{0,0,0,1}};
int n, mod;
long long a[4][4];
struct Matrix {
long long a[4][4];
Matrix() {
for(int i = 0; i < 4; ++i)
for(int j = 0; j < 4; ++j)
a[i][j] = 0;
}
Matrix(const long long a[4][4]) {
for(int i = 0; i < 4; ++i)
for(int j = 0; j < 4; ++j)
this->a[i][j] = a[i][j];
}
void operator *= (const Matrix &mat) {
Matrix res;
for(int i = 0; i < 4; ++i)
for(int j = 0; j < 4; ++j)
for(int k = 0; k < 4; ++k)
res.a[i][j] = (res.a[i][j] + a[i][k] * mat.a[k][j]) % mod;
*this = res;
}
Matrix operator ^ (const int &n) {
Matrix res = Matrix(base), now = *this;
for(int i = n; i != 0; i >>= 1) {
if(i & 1) res *= now;
now *= now;
}
return res;
}
};
int main() {
int tc; scanf("%d", &tc);
while(tc--) {
int a2; scanf("%d%d%d", &a2, &n, &mod);
memset(a, 0, sizeof a);
a[0][0] = a[1][2] = a[2][0] = a[2][1] = 1;
a[2][2] = 4LL * a2 * a2 % mod; a[2][3] = 2LL * a2 % mod;
a[3][2] = -4LL * a2 % mod; a[3][3] = -1;
Matrix res = Matrix(a) ^ (n-1);
printf("%lld\n", (((res.a[0][0] + res.a[1][0] + res.a[2][0] * a2 % mod * a2 % mod + res.a[3][0] * a2) % mod) + mod) % mod);
}
return 0;
}