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;
}

Download