FBRICK - Xếp hình
Tác giả: RR
Ngôn ngữ: C++
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define FOR(i,a,b) for(i=(a); i<=(b); i++)
#define REP(i,a) for(i=0; i<(a); i++)
#define ll long long
int base, a, n;
int m[2][16], p[32][16];
int INP,AM;
#define BUFSIZE (1<<12)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
if(!*inp) { \
if (feof(stdin)) memset(BUF, 0, sizeof BUF); else fread(BUF,1,BUFSIZE,stdin); \
inp=BUF; \
} \
INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
AM=0;\
GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
if (INP=='-') {AM=1;GETCHAR(INP);} \
j=INP-'0'; GETCHAR(INP); \
while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
if (AM) j=-j;\
}
int main() {
// freopen("tow1.in", "r", stdin);
// freopen("output.txt", "w", stdout);
int ntest; GN(ntest);
int need, i, j, u, v, k, b1, b2, c2, s2, cur, t;
while (ntest--) {
GN(a); GN(n); GN(base);
b1 = 1, b2 = (a * (ll)a) % base;
c2 = a, s2 = (b1 + b2) % base;
p[0][0] = p[0][5] = p[0][10] = p[0][15] = 1;
p[1][1] = 1;
p[1][4] = 1; p[1][5] = ((4 * (ll) a) % base * a) % base; p[1][6] = base - (4 * (ll) a) % base;
p[1][9] = (2*a) % base; p[1][10] = (base - 1);
p[1][12] = 1; p[1][13] = ((4 * (ll) a) % base * a) % base; p[1][14] = base - (4 * (ll) a) % base; p[1][15] = 1;
need = n-2;
REP(i,16) m[0][i] = p[0][i];
cur = 0, t = 0;
while ((1<<t) < need) t++;
t++;
FOR(i,1,t) {
if (i >= 2) {
REP(k,16) {
p[i][k] = 0;
for(u = k - (k&3), v = (k&3); v < 16; u++, v+=4) {
p[i][k] += (p[i-1][u] * (ll)p[i-1][v]) % base;
if (p[i][k] >= base) p[i][k] -= base;
}
}
}
if ((need >> (i-1)) & 1) {
REP(k,16) {
m[1-cur][k] = 0;
for(u = k - (k&3), v = (k&3); v < 16; u++, v+=4) {
m[1-cur][k] += (m[cur][u] * (ll)p[i][v]) % base;
if (m[1-cur][k] >= base) m[1-cur][k] -= base;
}
}
cur = 1 - cur;
}
}
int res = ((m[cur][12] * (ll) b1
+ m[cur][13] * (ll) b2) % base
+ (m[cur][14] * (ll) c2
+ m[cur][15] * (ll) s2) % base) % base;
printf("%d\n", (int) res);
}
return 0;
}