Editorial for Xếp hình

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;

long long base;

struct matrix
{
long long a[6][6];

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


Code mẫu của happyboy99x

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


program FBRICK;
uses    math;
const   fi = '';
fo = '';
type    arr = array[1..6,1..6] of int64;
var     s, c: arr;
Q:array[1..6] of int64;
n, m , k, res, kk: int64;
t, tt, i: longint;
inp, oup:text;

operator *(a,b: arr) c: arr;
var     i,j,k:longint;
begin
for i:=1 to 6 do
for j:=1 to 6 do begin
C[i,j] := 0;
for k:=1 to 6 do begin
C[i,j] := (C[i,j] + a[i,k]*b[k,j]) mod M;
end;
if c[i,j] < 0 then inc(c[i,j], m);
end;
end;

function Pow(p: longint):  arr;
var     t: arr;
begin
if p = 1 then exit(S);
t := Pow(p shr 1);
t := t * t;
if odd(p) then exit(t * S);
exit(t);
end;

begin
assign(inp,fi);reset(inp);
assign(oup,fo);rewrite(oup);
for tt:=1 to t do begin
k := 2*kk mod m;
Q[1] := 1; Q[2] := kk*kk mod m; Q[3] := 1;
Q[4] := kk; Q[5] := kk; Q[6] := 1;
S[1,1] := 1; S[1,2] := 1; S[2,2] := k*k mod m;
S[2,3] := 1; S[2,4] := -2*k; S[3,2] := 1;
S[4,2] := k; S[4,4] := -1; S[5,5] := k;
S[5,6] := -1; S[6,5] := 1;
C := Pow(n-1);
res := 0;
for i:=1 to 6 do begin
res := (res + Q[i] * C[1,i]) mod M;
//if res < 0 then inc(res, m);
end;
writeln(oup,res);
end;
close(oup);
end.


Code mẫu của RR

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


Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<sstream>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 111111111
//#define mod 1000000009
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, x) memset(a, x, sizeof(a))
#define SZ(a) (int)(a.size())
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
typedef long long ll;
const int max_size = 4;
ll mod;

struct Matrix{
ll x[max_size][max_size];
Matrix(){};
Matrix(int d){
MS(x, 0);
rep(i, max_size) x[i][i] = d;
};
Matrix(ll const a[max_size][max_size]) { for(int i = 0; i < max_size; i++) for(int j = 0; j < max_size; j++) x[i][j] = a[i][j];}
friend Matrix operator * (const Matrix &a, const Matrix &b){
Matrix c;
for(int i = 0; i < max_size; i++) for(int j = 0; j < max_size; j++){
c.x[i][j] = 0;
for(int k = 0; k < max_size; k++) c.x[i][j] = (c.x[i][j] + a.x[i][k] * b.x[k][j]) % mod;
}
return c;
}

friend Matrix operator ^ (const Matrix &a,const int &k){
Matrix base;
rep(i, max_size) rep(j, max_size) base.x[i][j] = a.x[i][j];
Matrix res = Matrix(1);
int p = k;
while (p > 0) {
if (p & 1) {
res = res * base;
}
p >>= 1;
base = base * base;
}
return res;
}

void print(){
for(int i = 0; i < max_size; i++){
for(int j = 0; j < max_size; j++) printf("%lld ",x[i][j]);
printf("\n");
}
}
};

int test;
ll x, k, n, m, a[5], f[5];

int main(){
//freopen("input.in","r",stdin);
//freopen("output.out","w",stdout);
cin >> test;
while(test --){
cin >> x >> n >> mod;
x %= mod;
a[1] = 1 % mod; f[1] = a[1];
a[2] = x ; f[2] = (a[1] * a[1] + a[2] * a[2]) %mod;
for(int i = 3; i <= 4; i++) {
a[i] =( 2 * x * a[i - 1] - a[i - 2]) % mod;
f[i] = (f[i - 1] + a[i] * a[i]) % mod;
}
if(n < 5) cout<<f[n]<<endl;

else {
k = (4 * x * x - 1) % mod;
ll u[4][4] = { (k + 1) % mod , 1, 0, 0,
mod - ((2 * k) % mod), 0, 1, 0,
(k + 1) % mod, 0, 0, 1,
mod - 1, 0, 0, 0};
Matrix A = Matrix(u);
A = A ^ (n - 4);
long long kq = 0;
for(int i = 0; i < 4; i++) kq = (kq + f[4 - i] * A.x[i][0]) % mod;
cout << kq << endl;
}
}
// getch();
}


Code mẫu của skyvn97

#include<cstdio>
typedef long long ll;
struct matrix {
int m,n;
ll d[10][10];
};
int n;
ll a2;
ll mod;
matrix fst,mul;
matrix multi(const matrix &a,const matrix &b) {
int i,j,k;
int x=a.m;
int y=a.n;
int z=b.n;
matrix c;
c.m=x;c.n=z;
for (i=0;i<x;i=i+1)
for (j=0;j<z;j=j+1) {
c.d[i][j]=0;
for (k=0;k<y;k=k+1)
c.d[i][j]=(c.d[i][j]+a.d[i][k]*b.d[k][j])%mod;
}
return (c);
}
matrix multiply(const matrix &a,const int &k) {
if (k==1) return (a);
matrix r=multiply(a,k/2);
r=multi(r,r);
if (k%2==1) r=multi(r,a);
return (r);
}
void process(void) {
scanf("%lld",&a2);
scanf("%d",&n);
scanf("%lld",&mod);
if (mod==1) {
printf("0\n");
return;
}
mul.m=4;
mul.n=4;
mul.d[0][0]=1;
mul.d[0][1]=0;
mul.d[0][2]=0;
mul.d[0][3]=0;
mul.d[1][0]=(4*a2*a2)%mod;
mul.d[1][1]=(4*a2*a2)%mod;
mul.d[1][2]=1;
mul.d[1][3]=(2*a2)%mod;
mul.d[2][0]=1;
mul.d[2][1]=1;
mul.d[2][2]=0;
mul.d[2][3]=0;
mul.d[3][0]=(-4*a2)%mod+mod;
mul.d[3][1]=(-4*a2)%mod+mod;
mul.d[3][2]=0;
mul.d[3][3]=mod-1;
fst.m=1;
fst.n=4;
fst.d[0][0]=(1+a2*a2)%mod;
fst.d[0][1]=(a2*a2)%mod;
fst.d[0][2]=1;
fst.d[0][3]=a2%mod;
if (n>2) fst=multi(fst,multiply(mul,n-2));
if (fst.d[0][0]<0) fst.d[0][0]+=mod;
printf("%lld\n",fst.d[0][0]);
}
int main(void) {
int t,c;
scanf("%d",&t);
for (c=1;c<=t;c=c+1) process();
return 0;
}