結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
![]() |
提出日時 | 2021-10-08 23:07:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 198 ms / 2,000 ms |
コード長 | 2,889 bytes |
コンパイル時間 | 2,652 ms |
コンパイル使用メモリ | 207,048 KB |
最終ジャッジ日時 | 2025-01-24 23:15:33 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)// Ref: https://qiita.com/ysuzuki19/items/d89057d65284ba1a16ac#define dump(var) do{std::cerr << #var << " : ";view(var);}while(0)template<typename T> void view(T e){std::cerr << e << "\n";}template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cerr << e << " "; } std::cerr << "\n";}template<typename T> void view(const std::vector<std::vector<T> >& vv){ std::cerr << "\n"; for(const auto& v : vv){ view(v); } }template<typename T> void dump_cout(const T& v) { for(long long i = 0; i < v.size(); i++) std::cout << v[i] << (i == v.size()-1 ? "\n" : " "); }namespace mm {template <class T> using matrix = std::vector<std::vector<T>>;template <class T>matrix<T> E(int n) {matrix<T> res(n, std::vector<T>(n, 0));for(int i = 0; i < n; i++) res[i][i] = 1;return res;}template <class T>matrix<T> matMul(matrix<T> a, matrix<T> b) {assert(a.size() && b.size());assert(a[0].size() == b.size());matrix<T> res(a.size(), std::vector<T>(b[0].size(), 0));for(int i = 0; i < a.size(); i++) {for(int j = 0; j < b[0].size(); j++) {for(int k = 0; k < b.size(); k++) {res[i][j] += a[i][k] * b[k][j];}}}return res;}template <class T>std::vector<T> vecMul(matrix<T> a, std::vector<T> b) {assert(a.size() && b.size());assert(a[0].size() == b.size());std::vector<T> res(b.size(), 0);for(int i = 0; i < a.size(); i++) {for(int j = 0; j < b.size(); j++) {res[i] += a[i][j] * b[j];}}return res;}template <class T>matrix<T> matPow(matrix<T> a, long long p) {assert(a.size() && a.size() == a[0].size());matrix<T> res(a.size(), std::vector<T>(a.size(), 0));for(int i = 0; i < a.size(); i++) res[i][i] = 1;while(p) {if(p & 1) res = matMul(res, a);a = matMul(a, a);p /= 2;}return res;}}using namespace mm;#include <atcoder/modint>using mint = atcoder::modint1000000007;void solve() {ll n;cin >> n;mint v = mint(3).inv();matrix<mint> M = {{v, 0, 0, 0, v, v},{0, v, 0, v, 0, v},{0, 0, v, v, v, 0},{1, 0, 0, 0, 0, 0},{0, 1, 0, 0, 0, 0},{0, 0, 1, 0, 0, 0}};vector<mint> V = {v, 0, 0, 1, 0, 0};auto RM = matPow(M, n);auto RV = vecMul(RM, V);cout << RV[3].val() << endl;}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);ll t;cin >> t;while(t--) solve();return 0;}