結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
![]() |
提出日時 | 2023-06-03 16:49:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 231 ms / 2,000 ms |
コード長 | 2,821 bytes |
コンパイル時間 | 1,458 ms |
コンパイル使用メモリ | 112,836 KB |
最終ジャッジ日時 | 2025-02-13 22:23:35 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
#include <iostream>#include <vector>#include <cmath>#include <map>#include <set>#include <iomanip>#include <queue>#include <algorithm>#include <numeric>#include <deque>#include <complex>#include <cassert>using namespace std;using ll = long long;const ll modc = 1e9+7;class mint {ll x;public:mint(ll x=0) : x((x%modc+modc)%modc) {}mint operator-() const {return mint(-x);}mint& operator+=(const mint& a) {if ((x += a.x) >= modc) x -= modc;return *this;}mint& operator-=(const mint& a) {if ((x += modc-a.x) >= modc) x -= modc;return *this;}mint& operator*=(const mint& a) {(x *= a.x) %= modc;return *this;}mint operator+(const mint& a) const {mint res(*this);return res+=a;}mint operator-(const mint& a) const {mint res(*this);return res-=a;}mint operator*(const mint& a) const {mint res(*this);return res*=a;}mint pow(ll t) const {if (!t) return 1;mint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}mint inv() const {return pow(modc-2);}mint& operator/=(const mint& a) {return (*this) *= a.inv();}mint operator/(const mint& a) const {mint res(*this);return res/=a;}bool operator == (const mint& a) const{return x == a.x;}friend ostream& operator<<(ostream& os, const mint& m){os << m.x;return os;}friend istream& operator>>(istream& ip, mint&m) {ip >> m.x;return ip;}};vector<vector<mint>> dot(vector<vector<mint>> &a, vector<vector<mint>> &b){int M = a.size();vector<vector<mint>> c(M, vector<mint>(M));for (int i=0; i<M; i++){for (int k=0; k<M; k++){for (int j=0; j<M; j++) c[i][j] += (a[i][k] * b[k][j]);}}return c;}//A^Nvector<vector<mint>> pow(vector<vector<mint>> A, ll N){int M = A.size();vector<vector<mint>> B(M, vector<mint>(M));for (int i=0; i<M; i++) B[i][i] = 1;while(N){if (N % 2 == 1) B = dot(B, A);N >>= 1;A = dot(A, A);}return B;}mint a;vector<vector<mint>> B(6, vector<mint>(6));void solve(){ll N;cin >> N;if (N == 1){cout << a << endl;return;}vector<vector<mint>> C = pow(B, N-1);cout << C[0][0] * a + C[0][3] << endl;}int main(){ll T;cin >> T;a = mint(3).inv();for (int i=0; i<3; i++){B[i][i] = a;B[3+i][i] = 1;for (int j=0; j<3; j++){if (i != j) B[i][j+3] = a;}}while(T){T--;solve();}return 0;}