結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
![]() |
提出日時 | 2021-10-08 23:44:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 612 ms / 2,000 ms |
コード長 | 1,204 bytes |
コンパイル時間 | 2,733 ms |
コンパイル使用メモリ | 201,264 KB |
最終ジャッジ日時 | 2025-01-24 23:36:22 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
#define rep(i,n) for(int i=0;i<(int)(n);i++)#define ALL(v) v.begin(),v.end()typedef long long ll;#include <bits/stdc++.h>using namespace std;#define MOD 1000000007vector<vector<ll>> matrixmul(ll m,vector<vector<ll>> a,vector<vector<ll>> b){vector<vector<ll>> c(m,vector<ll>(m,0));rep(i,m) rep(j,m) rep(k,m) c[i][j]=(c[i][j]+a[i][k]*b[k][j]%MOD)%MOD;return c;}vector<vector<ll>> matrixpow(ll m,vector<vector<ll>> vec,ll n){vector<vector<ll>> ans(m,vector<ll>(m,0));rep(i,m) ans[i][i]=1;while(n){if(n&1) ans=matrixmul(m,ans,vec);vec=matrixmul(m,vec,vec);n>>=1;}return ans;}ll modpow(ll x,ll n){ll ans=1;while(n){if(n&1) ans=ans*x%MOD;x=x*x%MOD;n/=2;}return ans;}int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);vector<vector<ll>> A(9,vector<ll>(9));A[0][0]=1,A[0][4]=1,A[0][8]=1;A[1][1]=1,A[1][3]=1,A[1][5]=1;A[2][2]=1,A[2][6]=1,A[2][7]=1;A[3][0]=3,A[4][1]=3,A[5][2]=3;A[6][1]=3,A[7][0]=3,A[8][2]=3;ll m=modpow(3,MOD-2);int t;cin>>t;while(t--){ll n;cin>>n;vector<vector<ll>> B=matrixpow(9,A,n);cout<<B[0][0]*modpow(m,n)%MOD<<endl;}return 0;}