Untitled
raw download clone
TEXT
views 11
,
size 3620 b
//
//  main.c
//  題庫 #12254
//
//  Created by Anna on 2020/6/19.
//  Copyright © 2020 Anna. All rights reserved.
//




#include <stdio.h>

long long mod = 10e9 + 7;
typedef struct{
    long long int m[5][5];
}mat;
long long MOD (long long A, long long B, long long C){
    return ((A+B) % mod + C) % mod;
}
mat A;
mat identity;
mat tmp;
mat mul(mat * x, mat * y){
    
    tmp.m[0][0] = MOD((x->m[0][0]%mod * y->m[0][0]%mod)%mod, (x->m[0][1]%mod * y->m[1][0]%mod)%mod, (x->m[0][2]%mod * y->m[2][0]%mod)%mod);
    tmp.m[0][1] = MOD((x->m[0][0]%mod * y->m[0][1]%mod)%mod, (x->m[0][1]%mod * y->m[1][1]%mod)%mod, (x->m[0][2]%mod * y->m[2][1]%mod)%mod);
    tmp.m[0][2] = MOD((x->m[0][0]%mod * y->m[0][2]%mod)%mod, (x->m[0][1]%mod * y->m[1][2]%mod)%mod, (x->m[0][2]%mod * y->m[2][2]%mod)%mod);
    
    tmp.m[1][0] = MOD((x->m[1][0]%mod * y->m[0][0]%mod)%mod, (x->m[1][1]%mod * y->m[1][0]%mod)%mod, (x->m[1][2]%mod * y->m[2][0]%mod)%mod);
    tmp.m[1][1] = MOD((x->m[1][0]%mod * y->m[0][1]%mod)%mod, (x->m[1][1]%mod * y->m[1][1]%mod)%mod, (x->m[1][2]%mod * y->m[2][1]%mod)%mod);
    tmp.m[1][2] = MOD((x->m[1][0]%mod * y->m[0][2]%mod)%mod, (x->m[1][1]%mod * y->m[1][2]%mod)%mod, (x->m[1][2]%mod * y->m[2][2]%mod)%mod);
     
    tmp.m[2][0] = MOD((x->m[2][0]%mod * y->m[0][0]%mod)%mod, (x->m[2][1]%mod * y->m[1][0]%mod)%mod, (x->m[2][2]%mod * y->m[2][0]%mod)%mod);
    tmp.m[2][1] = MOD((x->m[2][0]%mod * y->m[0][1]%mod)%mod, (x->m[2][1]%mod * y->m[1][1]%mod)%mod, (x->m[2][2]%mod * y->m[2][1]%mod)%mod);
    tmp.m[2][2] = MOD((x->m[2][0]%mod * y->m[0][2]%mod)%mod, (x->m[2][1]%mod * y->m[1][2]%mod)%mod, (x->m[2][2]%mod * y->m[2][2]%mod)%mod);
    return tmp;
}




mat fastpower(mat x, long long y){
    if (y == 0) return identity;
    mat res = fastpower(x, y / 2);
    mat ans = mul (&res, &res);
    if (y % 2 == 1) ans = mul (&ans, &x);
    return ans;
}




int main(void) {
    int t;
    long long x, Pn, Pa, Pb, Pc;
    mat ANS;
    
    //設定單位矩陣的內容
    for (int r = 0; r < 3; r++){
        for (int c = 0; c < 3; c++){
            if (r == c) identity.m[r][c] = 1 % mod;
            else identity.m[r][c] = 0;
        }
    }
    //設定A矩陣的內容
    A.m[0][0] = 1;
    A.m[0][1] = 2;
    A.m[0][2] = 1;
    A.m[1][0] = 1;
    A.m[2][1] = 1;
    A.m[1][1] = A.m[1][2] = A.m[2][0] = A.m[2][2] = 0;
    
    scanf("%d", &t);
    for (int i = 1; i <= t; i++){
        scanf ("%lld", &x);
        //若x<=3,直接輸出
        if (x == 1) printf ("1\n");
        else if (x == 2) printf ("12\n");
        else if (x == 3) printf ("13\n");
        //若x>3,用快速冪
        else {
            ANS = fastpower(A, x - 3);
            /*//輸出看ANS是否正確
            for (int r = 0; r < 3; r++){
                for (int c = 0; c < 3; c++){
                    printf ("%lld ", ANS.m[r][c]);
                }printf ("\n");
            }printf ("\n");*/
            //算Pn
            Pa = (ANS.m[0][0]%mod * 13%mod)%mod;
            Pb = (ANS.m[0][1]%mod * 12%mod)%mod;
            Pc = (ANS.m[0][2]%mod * 1%mod)%mod;
            
            //((a+b) mod p + c)mod p = (a + (b+c) mod p) mod p
            //再mod一次
            Pn = MOD (Pa, Pb, Pc);
            printf ("%lld\n", Pn);
        }
    }
    return 0;
}
close fullscreen
Login or Register to edit or fork this paste. It's free.