Torni

#include <iostream>
#include <vector>
#include <cassert>

typedef long long LL;

using namespace std;
LL mod = 1e9+7;

struct Matrix{
    vector<vector<LL> > M;
    LL n, m;
    Matrix(LL n, LL m) : n(n), m(m) {
        M = vector<vector<LL> >(n, vector<LL>(m));
    }
    Matrix operator*(const Matrix& B) {
        Matrix A = *this;
        assert(A.m == B.n);
        Matrix C(A.n, B.m);
        for(LL i = 0; i < C.n; i++){
            for(LL j = 0; j < C.m; j++){
                for(LL k = 0; k < A.m; k++){
                    C.M[i][j] = (C.M[i][j] + A.M[i][k] * B.M[k][j]) % mod;
                }
            }
        }
        return C;
    }

    static Matrix identity(LL n){
        Matrix I(n,n);
        for(LL i = 0; i < n; i++) I.M[i][i] = 1;
        return I;
    }
};

vector<Matrix> precalc_powers; // Epic säätö

Matrix matpow(Matrix M, LL k){
    Matrix ans = Matrix::identity(M.n);
    for(LL i = 1; k != 0; i++, k /= 2){
        if(k&1) ans = ans * precalc_powers[i];
    }
    return ans;
}

LL get_id(bool b1, bool b2, bool b3, bool b4, bool b5){
    return b1*1 + b2*2 + b3*4 + b4*8 + b5*16;
}

bool H(LL x, LL pos){
    return x & (1 << (pos-1));
}

// A below, B above
bool fits(LL A, LL B){
    if(H(A,1) != H(B,4)) return false;
    if(H(A,2) != H(B,5)) return false;
    if(!H(A,1) && !H(A,3) && (H(B,3) || H(B,5))) return false;
    if(!H(A,2) && !H(A,3) && (H(B,3) || H(B,4))) return false;
    if(!H(B,3) && !H(B,4) && (H(A,3) || H(A,2))) return false;
    if(!H(B,3) && !H(B,5) && (H(A,3) || H(A,1))) return false;
    return true;
}

void solve(){
    LL h; cin >> h;

    Matrix C(32,1); // State vector
    C.M[get_id(1,1,1,1,1)][0]++;
    C.M[get_id(0,1,1,1,1)][0]++;
    C.M[get_id(1,0,1,1,1)][0]++;
    C.M[get_id(0,0,1,1,1)][0]++;
    C.M[get_id(0,0,0,1,1)][0]++;
    C.M[get_id(1,1,0,1,1)][0]++;

    Matrix mat = precalc_powers[1];
    mat = matpow(mat,h-1);
    C = mat * C;
    LL ans = 0;
    for(LL A = 0; A < 32; A++){
        if(H(A,1) && H(A,2)) ans = (ans + C.M[A][0]) % mod;
    }
    cout << ans % mod << "\n";
}

void precalc(){

    Matrix mat(32,32);
    for(LL A = 0; A < 32; A++){
        for(LL B = 0; B < 32; B++){
            mat.M[B][A] = fits(A,B);
        }
    }
    precalc_powers.push_back(Matrix::identity(32));
    precalc_powers.push_back(mat);
    for(LL i = 0; i < 100; i++){
        precalc_powers.push_back(precalc_powers.back() * precalc_powers.back());
    }
}

int main(){
    precalc();
    LL t; cin >> t; while(t--) solve();
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED