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




#include <stdio.h>
//#include <math.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){
    //((a+b) mod p + c)mod p = (a + (b+c) mod p) mod p
    return ((A+B) % mod + C) % mod;
}
mat A;
mat identity;
mat tmp;
mat mul(mat * x, mat * y){
    /*
    tmp.m[0][0] = (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] = (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] = (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] = (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] = (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] = (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] = (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] = (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] = (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
    ;*/
    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){//2 1 0
    if (y == 0) return identity; //要%m,因為當m=1時,答案應為0,但若沒有%m,答案會是1。
    mat res = fastpower(x, y / 2);//res = fastpower(A, 1); res = fastpower(A, 0) = identity
    mat ans = mul (&res, &res); // ans = identity
    if (y % 2 == 1) ans = mul (&ans, &x); //x^5 = x^2 * x^2 * x (因為5 / 2 = 2,所以會少乘一次)
    return ans;//(identity * x)^2
}




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 = ((Pa + Pb)%mod + Pc)%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.