Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- #define ull long long
- typedef vector<vector<ull>> Matrix;
- const ull MOD = 1000000007;
- Matrix multiply(const Matrix& A, const Matrix& B) {
- ull n = A.size();
- Matrix result(n, vector<ull>(n, 0));
- for (ull i = 0; i < n; ++i) {
- for (ull j = 0; j < n; ++j) {
- for (ull k = 0; k < n; ++k) {
- result[i][j] =
- (result[i][j] + (ull)A[i][k] * B[k][j] % MOD) % MOD;
- }
- }
- }
- return result;
- }
- Matrix matrixPower(Matrix M, ull exp) {
- ull n = M.size();
- Matrix result(n, vector<ull>(n, 0));
- for (ull i = 0; i < n; ++i) {
- result[i][i] = 1;
- }
- while (exp > 0) {
- if (exp % 2 == 1) {
- result = multiply(result, M);
- }
- M = multiply(M, M);
- exp /= 2;
- }
- return result;
- }
- ull matrixExponentiation(ull N) {
- Matrix M = {{0, 2, 1, 0}, {1, 0, 0, 1}, {1, 0, 0, 0}, {0, 1, 0, 0}};
- vector<ull> V2 = {0, 1, 1, 0};
- if (N == 1) {
- return V2[0];
- }
- Matrix M_power = matrixPower(M, N - 1);
- ull result = 0;
- for (ull i = 0; i < 4; ++i) {
- result = (result + (ull)M_power[0][i] * V2[i] % MOD) % MOD;
- }
- return result;
- }
- int main() {
- ull N;
- cin >> N;
- cout << matrixExponentiation(N);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement