結果
問題 |
No.1810 RGB Biscuits
|
ユーザー |
|
提出日時 | 2022-01-14 22:12:30 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 26 ms / 2,000 ms |
コード長 | 1,994 bytes |
コンパイル時間 | 7,653 ms |
コンパイル使用メモリ | 163,400 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-20 11:09:02 |
合計ジャッジ時間 | 6,247 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
/* * Author: nskybytskyi * Time: 2022-01-13 15:08:45 */ #include <bits/stdc++.h> using namespace std; const int64_t mod = 1'000'000'007; using matrix = vector<vector<int64_t>>; const matrix eye = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}; vector<int64_t> mmul(matrix lhs, vector<int64_t> rhs) { vector<int64_t> res(3); for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { res[i] += lhs[i][j] * rhs[j]; res[i] %= mod; } } return res; } matrix mmul(matrix lhs, matrix rhs) { matrix ans(3, vector<int64_t>(3, 0)); for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { for (int k = 0; k < 3; ++k) { ans[i][j] += lhs[i][k] * rhs[k][j]; ans[i][j] %= mod; } } } return ans; } matrix mpow(matrix base, int64_t exponent) { matrix res = eye; while (exponent) { if (exponent & 1) { res = mmul(res, base); } base = mmul(base, base); exponent >>= 1; } return res; } int main() { cin.tie(0)->sync_with_stdio(0); int a, b, n; cin >> a >> b >> n; vector<pair<int64_t, int>> t(n); for (int i = 0; i < n; ++i) { cin >> t[i].first; t[i].second = i; } sort(t.begin(), t.end()); matrix e = {{1, 0, 0}, {0, 1, 0}, {a, b, 1}}, o = {{0, 0, 1}, {1, 0, 0}, {0, 0, 0}}; matrix eo = mmul(e, o), oe = mmul(o, e); vector<int64_t> curr = {1, 1, 0}; int64_t time = 0; vector<int64_t> ans(n); for (auto [ti, i] : t) { if (time & 1) { if (ti & 1) { curr = mmul(mpow(eo, (ti - time) / 2), curr); } else { curr = mmul(o, curr); curr = mmul(mpow(oe, (ti - time) / 2), curr); } } else { if (ti & 1) { curr = mmul(e, curr); curr = mmul(mpow(eo, (ti - time) / 2), curr); } else { curr = mmul(mpow(oe, (ti - time) / 2), curr); } } time = ti; ans[i] = (curr[0] + curr[1] + curr[2]) % mod; } for (auto elem : ans) { cout << elem << "\n"; } return 0; }