ProgrammingHub/mat_exp.txt at master · baljeetkumar/ProgrammingHub · 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
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
void multiply(ll a[2][2], ll b[2][2])
{
    ll mul[2][2];
    for (ll i = 0; i < 2; i++)
    {
        for (ll j = 0; j < 2; j++)
        {
            mul[i][j] = 0;
            for (ll k = 0; k < 2; k++)
                mul[i][j] =(mul[i][j]+ a[i][k]*b[k][j])%mod;
        }
    }
    for (ll i=0; i<2; i++)
        for (ll j=0; j<2; j++)
            a[i][j] = mul[i][j];
}
ll power( ll n)
{    ll F[2][2] = {{1,1}, {1,0}};
    ll res[2][2]={{1,0},{0,1}};
    ll M[2][2] = {{1,1}, {1,0}};
    // F[0][0]=1;F[0][1]=1;F[1][0]=1;F[1][1]=0;
    if (n==1)
        return F[0][0] ;

    //power(F, n/2);
while(n>0){


    if (n%2 != 0)
        multiply(res, F);
        multiply(F, F);
        n/=2;
}
    return res[0][0]  ;
}
ll po(ll a,ll b){
ll re=1;
while(b){
    if(b%2==1)re=(re*a)%mod;
    a=(a*a)%mod;
    b=b/2;
}
return re;
}

int main()
{  ios_base::sync_with_stdio(false);
cin.tie(0);
     ll t,n,m;

ll v[50];


for(ll i=2;i<=44;i++)
{v[i-2]=power(i-1);
}
cin>>t;
while(t--){
       cin>>n;
ll m=power(n-1)%mod;
ll b=0,no;
for(ll i=0;i<43;i++){
    if(b+v[i+1]-v[i]-1<n){
        b=b+v[i+1]-v[i]-1;
    }
    else if(b+v[i+1]-v[i]==n)  {no=v[i+1]+1;break;}
    else {
        no=v[i]+n-b;break;
    }
}
cout<<po(no,m)<<endl;

   }

   return 0;
}