結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
![]() |
提出日時 | 2021-10-08 23:17:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 291 ms / 2,000 ms |
コード長 | 2,233 bytes |
コンパイル時間 | 4,533 ms |
コンパイル使用メモリ | 205,120 KB |
最終ジャッジ日時 | 2025-01-24 23:21:39 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/modint>using namespace std;using namespace atcoder;//using mint = modint998244353;using mint = modint1000000007;using ll = long long;using ld = long double;using pll = pair<ll, ll>;using tlll = tuple<ll, ll, ll>;constexpr ll INF = 1LL << 60;template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}ll safemod(ll A, ll M) {return (A % M + M) % M;}ll divfloor(ll A, ll B) {if (B < 0) {return divfloor(-A, -B);} return (A - safemod(A, B)) / B;}ll divceil(ll A, ll B) {if (B < 0) {return divceil(-A, -B);} return divfloor(A + B - 1, B);}#define FINALANS(A) do {cout << (A) << '\n'; exit(0);} while (false)using mmat = vector<vector<mint>>;mmat mmatrixprod(mmat &A1, mmat &A2){ll n1 = A1.size(), n2 = A2.size();ll m1 = A1.front().size(), m2 = A2.front().size();if (n2 != m1){cerr << "Error: matrix product is not defined\n";abort();}mmat ret(n1, vector<mint>(m2, 0));for (ll i = 0; i < n1; i++){for (ll j = 0; j < m2; j++){for (ll k = 0; k < n2; k++){ret[i][j] += A1[i][k] * A2[k][j];}}}return ret;}mmat mmatrixpow(mmat &A1, ll k){ll n = A1.size();mmat A10(n, vector<mint>(n, 0));for (ll i = 0; i < n; i++){for (ll j = 0; j < n; j++){A10[i][j] = A1[i][j];}}mmat ret(n, vector<mint>(n, 0));for (ll i = 0; i < n; i++){ret[i][i] = 1;}while (k > 0){if ((k & 1) != 0)ret = mmatrixprod(ret, A10);A10 = mmatrixprod(A10, A10);k >>= 1;}return ret;}int main(){const mint inv3 = mint(1) / 3;mmat A = {{inv3, 0, 0, 0, inv3, inv3},{0, inv3, 0, inv3, 0, inv3},{0, 0, inv3, inv3, inv3, 0},{1, 0, 0, 0, 0, 0},{0, 1, 0, 0, 0, 0},{0, 0, 1, 0, 0, 0}};ll T;cin >> T;for (ll t = 0; t < T; t++){ll N;cin >> N;mmat pwA = mmatrixpow(A, N - 1);mmat x = {{inv3}, {0}, {0}, {1}, {0}, {0}};mmat y = mmatrixprod(pwA, x);mint ans = y.at(0).at(0);cout << ans.val() << '\n';}}