AlgorithmsLibrary/MatrixMultiplication.cpp at master · PawanAIT/AlgorithmsLibrary · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#define_USE_MATH_DEFINES
#include<bits/stdc++.h>
usingnamespacestd;
#defineLLlonglong
#definemp make_pair
#definepb push_back
#defineLDlongdouble
#definegc getchar_unlocked
#definepc putchar_unlocked
#definebitcount _builtin_popcount
#defineMOD1000000007
#defineMAXN1<<10
#definePI3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117068

int T,N,i,j;
template<typename T>T absll(T X)
{
if(X<0)
 {
return -1*X;
 }
else
return X;
}
voidmulAR(LL A[4][4],LL R[4])
{
LL x=(A[0][0]*R[0])%MOD+(A[0][1]*R[1])%MOD+(A[0][2]*R[2])%MOD+(A[0][3]*R[3])%MOD;
 x%=MOD;
LL y=(A[1][0]*R[0])%MOD+(A[1][1]*R[1])%MOD+(A[1][2]*R[2])%MOD+(A[1][3]*R[3])%MOD;
 y%=MOD;
LL z=(A[2][0]*R[0])%MOD+(A[2][1]*R[1])%MOD+(A[2][2]*R[2])%MOD+(A[2][3]*R[3])%MOD;
 z%=MOD;
LL w=(A[3][0]*R[0])%MOD+(A[3][1]*R[1])%MOD+(A[3][2]*R[2])%MOD+(A[3][3]*R[3])%MOD;
 w%=MOD;

 R[0]=x;
 R[1]=y;
 R[2]=z;
 R[3]=w;
}

voidmulAA(LL A[4][4],LL R[4][4])
{
LL L[4][4];
memset(L,0,sizeof(L));
 L[0][0]=(A[0][0]*R[0][0])%MOD+(A[0][1]*R[1][0])%MOD+(A[0][2]*R[2][0])%MOD+(A[0][3]*R[3][0])%MOD;
 L[0][0]%=MOD;
 L[0][1]=(A[0][0]*R[0][1])%MOD+(A[0][1]*R[1][1])%MOD+(A[0][2]*R[2][1])%MOD+(A[0][3]*R[3][1])%MOD;
 L[0][1]%=MOD;
 L[0][2]=(A[0][0]*R[0][2])%MOD+(A[0][1]*R[1][2])%MOD+(A[0][2]*R[2][2])%MOD+(A[0][3]*R[3][2])%MOD;
 L[0][2]%=MOD;
 L[0][3]=(A[0][0]*R[0][3])%MOD+(A[0][1]*R[1][3])%MOD+(A[0][2]*R[2][3])%MOD+(A[0][3]*R[3][3])%MOD;
 L[0][3]%=MOD;

 L[1][0]=(A[1][0]*R[0][0])%MOD+(A[1][1]*R[1][0])%MOD+(A[1][2]*R[2][0])%MOD+(A[1][3]*R[3][0])%MOD;
 L[1][0]%=MOD;
 L[1][1]=(A[1][0]*R[0][1])%MOD+(A[1][1]*R[1][1])%MOD+(A[1][2]*R[2][1])%MOD+(A[1][3]*R[3][1])%MOD;
 L[1][1]%=MOD;
 L[1][2]=(A[1][0]*R[0][2])%MOD+(A[1][1]*R[1][2])%MOD+(A[1][2]*R[2][2])%MOD+(A[1][3]*R[3][2])%MOD;
 L[1][2]%=MOD;
 L[1][3]=(A[1][0]*R[0][3])%MOD+(A[1][1]*R[1][3])%MOD+(A[1][2]*R[2][3])%MOD+(A[1][3]*R[3][3])%MOD;
 L[1][3]%=MOD;

 L[2][0]=(A[2][0]*R[0][0])%MOD+(A[2][1]*R[1][0])%MOD+(A[2][2]*R[2][0])%MOD+(A[2][3]*R[3][0])%MOD;
 L[2][0]%=MOD;
 L[2][1]=(A[2][0]*R[0][1])%MOD+(A[2][1]*R[1][1])%MOD+(A[2][2]*R[2][1])%MOD+(A[2][3]*R[3][1])%MOD;
 L[2][1]%=MOD;
 L[2][2]=(A[2][0]*R[0][2])%MOD+(A[2][1]*R[1][2])%MOD+(A[2][2]*R[2][2])%MOD+(A[2][3]*R[3][2])%MOD;
 L[2][2]%=MOD;
 L[2][3]=(A[2][0]*R[0][3])%MOD+(A[2][1]*R[1][3])%MOD+(A[2][2]*R[2][3])%MOD+(A[2][3]*R[3][3])%MOD;
 L[2][3]%=MOD;

 L[3][0]=(A[3][0]*R[0][0])%MOD+(A[3][1]*R[1][0])%MOD+(A[3][2]*R[2][0])%MOD+(A[3][3]*R[3][0])%MOD;
 L[3][0]%=MOD;
 L[3][1]=(A[3][0]*R[0][1])%MOD+(A[3][1]*R[1][1])%MOD+(A[3][2]*R[2][1])%MOD+(A[3][3]*R[3][1])%MOD;
 L[3][1]%=MOD;
 L[3][2]=(A[3][0]*R[0][2])%MOD+(A[3][1]*R[1][2])%MOD+(A[3][2]*R[2][2])%MOD+(A[3][3]*R[3][2])%MOD;
 L[3][2]%=MOD;
 L[3][3]=(A[3][0]*R[0][3])%MOD+(A[3][1]*R[1][3])%MOD+(A[3][2]*R[2][3])%MOD+(A[3][3]*R[3][3])%MOD;
 L[3][3]%=MOD;

for(i=0;i<4;i++)
 {
for(j=0;j<4;j++)
 {
 A[i][j]=L[i][j];
 }
 }

}
voidpower(LL A[4][4],int N)
{
if(N==0||N==1)
 {
return;
 }
LL B[4][4]={{5,-8,5,-1},{1,0,0,0},{0,1,0,0},{0,0,1,0}};
power(A,N/2);
mulAA(A,A);
if(N%2)
mulAA(A,B);
}

LLsolve(int N)
{
LL A[4][4]={{5,-8,5,-1},{1,0,0,0},{0,1,0,0},{0,0,1,0}};
LL R[4]={17,5,1,0};
power(A,N-1);
mulAR(A,R);
return (R[0]+MOD)%MOD;
}
intmain()
{
	cin>>T;
while(T--)
	{
 cin>>N;
if(N==1)
 {
 cout<<"0"<<endl;
 }
elseif(N==2)
 {
 cout<<"1"<<endl;
 }
elseif(N==3)
 {
 cout<<"5"<<endl;
 }
elseif(N==4)
 {
 cout<<"17"<<endl;
 }
else
 {
 cout<<solve(N-3)<<endl;
 }
	}
return0;
}