SHOW:
|
|
- or go back to the newest paste.
| 1 | #include <iostream> | |
| 2 | #include <cstring> | |
| 3 | #define MOD 1000000007 | |
| 4 | using namespace std; | |
| 5 | int a[80][10][10], sol[10][10], mat[10][10], t, i, l, c, j; | |
| 6 | long long n, p; | |
| 7 | int main() | |
| 8 | {
| |
| 9 | cin >> t; | |
| 10 | - | a[0][1][1] = a[0][3][3] = 3; |
| 10 | + | a[0][1][1] = -1; |
| 11 | - | a[0][1][2] = a[0][4][1] = 1; |
| 11 | + | a[0][3][3] = 3; |
| 12 | - | a[0][3][1] = -1; |
| 12 | + | a[0][1][2] = a[0][3][4] = 1; |
| 13 | a[0][3][1] = 3; | |
| 14 | for(i = 0; (1LL<<i) <= 1000000000LL; i++) | |
| 15 | {
| |
| 16 | for(l = 1; l <= 4; l++) | |
| 17 | for(c = 1; c <= 4; c++) | |
| 18 | for(j = 1; j <= 4; j++) | |
| 19 | {
| |
| 20 | a[i+1][l][c] += ((long long)a[i][l][j]*a[i][j][c])%MOD; | |
| 21 | if(a[i+1][l][c] > MOD) a[i+1][l][c] -= MOD; | |
| 22 | } | |
| 23 | } | |
| 24 | while(t--) | |
| 25 | {
| |
| 26 | cin >> n; | |
| 27 | p = n; | |
| 28 | memset(sol, 0, sizeof(sol)); | |
| 29 | sol[1][1] = sol[2][2] = sol[3][3] = sol[4][4] = 1; | |
| 30 | for(i = 0; (1LL<<i) <= p; i++) | |
| 31 | if((1LL<<i)&p) | |
| 32 | {
| |
| 33 | memset(mat, 0, sizeof(mat)); | |
| 34 | for(l = 1; l <= 4; l++) | |
| 35 | for(c = 1; c <= 4; c++) | |
| 36 | for(j = 1; j <= 4; j++) | |
| 37 | {
| |
| 38 | mat[l][c] += ((long long)sol[l][j]*a[i][j][c])%MOD; | |
| 39 | if(mat[l][c] > MOD) mat[l][c] -= MOD; | |
| 40 | } | |
| 41 | memcpy(sol, mat, sizeof(mat)); | |
| 42 | } | |
| 43 | cout << 4*sol[1][2] << "\n"; //MODULO! | |
| 44 | ||
| 45 | } | |
| 46 | return 0; | |
| 47 | } | |
| 48 | // | |
| 49 | //4*3*3*3*2 | |
| 50 | //4*3*3*3*3*3= | |
| 51 | // | |
| 52 | //D[i] = prod[i-1] * 3 - D[i-1] | |
| 53 | // | |
| 54 | //(D[i], D[i-1], prod[i], prod[i-1]) * | |
| 55 | - | // 3 1 0 0 |
| 55 | + | // (12 4 12 4) |
| 56 | - | // 0 0 0 0 |
| 56 | + | // -1 1 0 0 |
| 57 | - | //-1 0 3 0 |
| 57 | + | // 0 0 0 0 |
| 58 | - | // 0 0 0 1 |
| 58 | + | // 3 0 3 1 |
| 59 | // 0 0 0 0 | |
| 60 | // (24 12 36 12) | |
| 61 | // | |
| 62 | //= (D[i+1] D[i] prod[i+1] prod[i]) |
