Simple C++ ME code


#1

#define mod 1000000007

vector<vector> multiply(vector<vector> &A, vector<vector> &B) {
vector<vector> C = { {0,0},{0,0} };

for (int i = 0; i < 2; i++) {
	for (int j = 0; j < 2; j++) {
		long long sum = 0;
		for (int k = 0; k < 2; k++)
			sum = (sum + (A[i][k] * B[k][j]) % mod) % mod;
		C[i][j] = sum;
	}
}
return C;

}

void mat_pow(vector<vector> &mat, int n) {
vector<vector> ans = { {1,0},{0,1} };
while (n > 0) {
if(n&1){
ans = multiply(ans,mat);
}
mat = multiply(mat,mat);
n >>= 1;
}
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
mat[i][j] = ans[i][j];
}
}
}

int Solution::solve(int A) {
if (A == 0) return 0;
if (A <= 1) return 1;
vector<vector> mat = { {1,1},{1,0} };
mat_pow(mat,A-1);

return mat[0][0];

}