結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
|
提出日時 | 2021-10-11 23:03:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 116 ms / 2,000 ms |
コード長 | 1,919 bytes |
コンパイル時間 | 2,580 ms |
コンパイル使用メモリ | 202,560 KB |
最終ジャッジ日時 | 2025-01-25 00:12:06 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <math.h>#include <iomanip>#include <cstdint>#include <string>#include <sstream>template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }#define rep(i,n) for (int i = 0; i < (n); ++i)typedef long long ll;typedef long double ld;typedef unsigned long long ull;using P=pair<ll,ll>;const ll INF=1e18;const int mod=1e9+7;typedef vector<ll> vec;typedef vector<vec> mat;mat mul(mat &A,mat &B){mat C(A.size(),vec(B[0].size()));rep(i,A.size()){rep(k,B.size()){rep(j,B[0].size()){C[i][j]=(C[i][j]+A[i][k]*B[k][j])%mod;}}}return C;}mat pow(mat A,ll n){mat B(A.size(),vec(A.size()));rep(i,A.size()){B[i][i]=1;}while(n>0){if(n&1){B=mul(B,A);}A=mul(A,A);n>>=1;}return B;}ll mod_pow(ll x,ll n,ll m){if(n==0){return 1;}ll res=mod_pow(x*x%m,n/2,m);if(n&1){res=res*x%m;}return res;}mat a={{1,0,0,0,1,1},{0,1,0,1,0,1},{0,0,1,1,1,0},{3,0,0,0,0,0},{0,3,0,0,0,0},{0,0,3,0,0,0},};mat b={ {1},{0},{0},{3},{0},{0} };void solve(){ll n;cin>>n;auto x=pow(a,n);auto t=mul(x,b);ll div=mod_pow( mod_pow(3,mod-2,mod) ,n+1,mod);ll ans=t[3][0]*div%mod;cout<<ans<<endl;}int main(){ios_base::sync_with_stdio(false);cin.tie(NULL);int t;cin>>t;rep(i,t){solve();}return 0;}