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

Download