結果
問題 | No.1704 Many Bus Stops (easy) |
ユーザー |
|
提出日時 | 2021-10-16 20:37:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 32 ms / 2,000 ms |
コード長 | 1,243 bytes |
コンパイル時間 | 2,352 ms |
コンパイル使用メモリ | 204,832 KB |
最終ジャッジ日時 | 2025-01-25 01:42:53 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>using namespace std;long long t, n, m, w;const long long M = 1e9 + 7;typedef vector<vector<long long>> mat;long long powm(long long a, long long b) {long long u = 1, v = a;while (b > 0) {if (b & 1)u = u * v % M;v = v * v % M;b >>= 1;}return u;}mat mprod(mat& a, mat& b) {mat c(a.size(), vector<long long>(b[0].size()));for (int i = 0; i < a.size(); i++) {for (int k = 0; k < b.size(); k++) {for (int j = 0; j < b[0].size(); j++) {c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % M;}}}return c;}mat powmat(mat a, long long t) {mat b(a.size(), vector<long long>(a.size()));for (int i = 0; i < a.size(); i++)b[i][i] = 1;while (t > 0) {if (t & 1)b = mprod(b, a);a = mprod(a, a);t >>= 1;}return b;}int main(){cin >> t;w = powm(3, M - 2);for (int i = 0; i < t; i++) {cin >> n;mat a = { {w, M - w}, {1, 0} };mat d = powmat(a, n);m = (d[1][0] * 2 * powm(9, M - 2) % M + d[1][1] * 2 * powm(3, M - 2) % M) % M;m = (m + powm(5, M - 2)) % M;long long x = 2 * powm(15, M - 2) % M * powm(2, n) % M * powm(w, n) % M;if (n % 2 == 0)m = (m + x) % M;elsem = (m + M - x) % M;cout << m << endl;}}