FBRICK - Xếp hình

Tác giả: hieult

Ngôn ngữ: C++

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

Download