code. compile. run. debug. share.
Source Code
Language
/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <iostream>
#include <bits/stdc++.h>
#include <vector>
using namespace std;
#define ll long long
#define MOD 1000000007
vector<ll> b;
vector<vector<ll>> multiply(vector<vector<ll>> A, vector<vector<ll>> B)
{
vector<vector<ll>> C(3, vector<ll>(3));
for (ll i = 1; i <= 2; i++)
{
for (int j = 1; i <= 2; j++)
{
for (int x = 1; x <= 2; x++)
{
C[i][j] = (C[i][j] % MOD + (A[i][x] * B[x][j]) % MOD) % MOD;
}
}
}
return C;
}
vector<vector<ll>> power(vector<vector<ll>> A, ll p)
{
if (p == 1)
{
return A;
}
// when p is odd
if (p & 1)
{
return multiply(A, power(A, p - 1));
}
vector<vector<ll>> X = power(A, p / 2);
return multiply(X, X);
}
ll compute(ll n)
{
if (n == 0)
{
return 0;
}
if (n <= 6)
{
return b[n - 1];
}
//F1 derived from b
vector<ll> F1 = {0, 1, 1};
// Formation of Transformation matrix
// 0 1
// 1 1
vector<vector<ll>> T(3, vector<ll>(3));
for (ll i = 1; i <= 2; i++)
{
for (ll j = 1; j <= 2; j++)
{
if (i == 1 && j == 1)
{
T[i][j] = 0;
}
else
{
T[i][j] = 1;
}
}
}
T = power(T, n - 1);
// calculating nth term
ll res = 0;
for (int i = 1; i <= 2; i++)
{
res = (res % MOD + (T[1][i] * F1[i]) % MOD) % MOD;
}
return res;
}
int main()
{
int t;
cin >> t;
//fib array
b = {1, 1, 2, 3, 5, 8};
while (t--)
{
ll n;
cin >> n;
cout << compute(n) << endl;
}
return 0;
}
Compiling Program...
Standard Input:
Interactive Console
Text
Program is not being debugged. Click "Debug" button to start program in debug mode.
| # | Function | File:Line |
|---|
| Variable | Value |
|---|
| Register | Value |
|---|
| Expression | Value |
|---|
| # | Description |
|---|