Untitled
unknown
plain_text
2 years ago
1.2 kB
11
Indexable
#include<bits/stdc++.h> using namespace std; long long mod=1e15+7; long long n; long long a[5][5],b[5][5],goc[5][5]; void nhan(long long x[5][5],long long y[5][5]){ long long tam[5][5]; for(int i=1;i<=4;i++){ for(int j=1;j<=4;j++){ long long res=0; for(int k=1;k<=4;k++){ res = res + (x[i][k]%mod * y[k][j]%mod)%mod; res = res % mod; } tam[i][j]=res; } } for(int i=1;i<=4;i++){ for(int j=1;j<=4;j++){ a[i][j]=tam[i][j]; } } } void lt(long long x){ if(x==1) return; lt(x/2); nhan(a,a); if(x%2==1) nhan(a,b); } int main(){ int tc; cin >> tc; while(tc--){ cin >> n; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(goc,0,sizeof(goc)); a[1][1]=1, a[1][2]=1 ,a[1][3]=1,a[1][4]=1; a[2][2]=1, a[2][3]=1, a[2][4]=1; a[3][2]=1, a[4][3]=1; b[1][1]=1, b[1][2]=1 ,b[1][3]=1,b[1][4]=1; b[2][2]=1, b[2][3]=1, b[2][4]=1; b[3][2]=1, b[4][3]=1; goc[1][1]=6,goc[2][1]=3,goc[3][1]=2,goc[4][1]=1; if(n==0) cout << "0" << endl; if(n==1) cout << "1" << endl; if(n==2) cout << "3" << endl; if(n==3) cout << "6" << endl; if(n>3){ lt(n-3); nhan(a,goc); cout << a[1][1] << endl; } } return 0; }
Editor is loading...