fork download
copy 
  1.     #include <bits/stdc++.h>
  2.     #define pb push_back
  3.     #define MOD 1000000007
  4.  
  5.     using namespace std;
  6.  
  7.     typedef long long ll;
  8.     typedef long double ld;
  9.  
  10.     vector<vector<ll>> defaultMatrix = {{0,0,1}, {1,0,1}, {0,1,0}};
  11.     vector<vector<ll>> multiplicationResult(3);
  12.     vector<ll> finalResult;
  13.  
  14.     void multiplyMatrix(vector<vector<ll>> &mat, vector<vector<ll>> &mat2) {
  15.     	for(int i = 0; i < 3; i++)
  16.     		multiplicationResult[i].clear();
  17.  
  18.     	for(ll i = 0; i < 3; i++) {
  19.     		for(ll j = 0; j < 3; j++) {
  20.     			ll sum = 0;
  21.     			for(ll k = 0; k < 3; k++) {
  22.     				ll temp = (mat[i][k]%MOD * mat2[k][j]%MOD)%MOD;
  23.     				sum = (sum%MOD + temp%MOD)%MOD;
  24.     			}
  25.     			multiplicationResult[i].pb(sum);
  26.     		}
  27.     	}
  28.     	mat = multiplicationResult;
  29.     }
  30.  
  31.     void vecMultiply(vector<ll> &v, vector<vector<ll>> &mat) {
  32.     	finalResult.clear();
  33.     	for(ll i = 0; i < 3; i++) {
  34.     		ll sum = 0;
  35.     		for(ll j = 0; j < 3; j++) {
  36.     			ll temp = (v[j]%MOD * mat[j][i]%MOD)%MOD;
  37.     			sum = (sum%MOD + temp%MOD)%MOD;
  38.     		}
  39.     		finalResult.pb(sum);
  40.     	}
  41.     	v = finalResult;
  42.     }
  43.  
  44.     void exponentiate(vector<vector<ll>> &mat, ll n) {
  45.     	if(n == 0 || n == 1)
  46.     		return;
  47.     	exponentiate(mat, n / 2);
  48.     	multiplyMatrix(mat, mat);
  49.     	if(n&1)
  50.     		multiplyMatrix(mat, defaultMatrix);
  51.     }
  52.  
  53.     ll matrixExponentiation(ll n) {
  54.     	vector<vector<ll>> mat = defaultMatrix;
  55.     	vector<ll> v = {1, 0, 1};
  56.     	if(n <= 2)
  57.     		return v[n];
  58.     	exponentiate(mat, n - 2);
  59.     	vecMultiply(v, mat);
  60.     	return v[2];
  61.     }
  62.  
  63.     int main() {
  64.         ios_base::sync_with_stdio(false);
  65.         cin.tie(NULL);
  66.         ll t;
  67.         cin>>t;
  68.         while(t--) {
  69.         	ll n;
  70.         	cin>>n;
  71.         	ll matrix = matrixExponentiation(n);
  72.         	cout<<matrix<<endl;
  73.         }
  74.  
  75.         return 0;
  76.     }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
2
5
1
stdout
copy 
2
0
https://ideone.com/2HOmP3
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!