結果
問題 | No.1810 RGB Biscuits |
ユーザー |
![]() |
提出日時 | 2021-09-18 13:28:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 19 ms / 2,000 ms |
コード長 | 1,286 bytes |
コンパイル時間 | 938 ms |
コンパイル使用メモリ | 79,536 KB |
最終ジャッジ日時 | 2025-01-24 15:42:42 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <iostream> #include <vector> #define rep(i, l, n) for (int i = (l); i < (n); i++) using namespace std; using ll = long long; template <class T> using V = vector<T>; template <class T> using VV = V<V<T> >; const ll mod = 1000000007; VV<ll> matrix_prod(const VV<ll>&A, const VV<ll>&B) { VV<ll> res = { {0,0},{0,0} }; rep(i, 0, 2) { rep(j, 0, 2) { rep(k, 0, 2) { res[i][j] += A[i][k] * B[k][j]; res[i][j] %= mod; } } } return res; } VV<ll> matrix_exp(VV<ll>A, ll n) { VV<ll> res = { {1,0},{0,1} }; while (n) { if (n & 1) { res = matrix_prod(A, res); } A = matrix_prod(A, A); n >>= 1; } return res; } V<ll> P_convertion(const VV<ll>& A, const V<ll>& v) { V<ll> res = { 0,0 }; rep(i, 0, 2) { rep(j, 0, 2) { res[i] += A[i][j] * v[j]; res[i] %= mod; } } return res; } int main(void) { ll a, b; cin >> a >> b; int n; cin >> n; V<ll> t(n); rep(i, 0, n) { cin >> t[i]; } VV<ll> A = { {a,b},{1,0} }; V<ll> v = { 1,1 }; rep(i, 0, n) { ll d = t[i] >> 1; int r = t[i] & 1; VV<ll> Ad = matrix_exp(A, d); V<ll> v1 = P_convertion(Ad, v); V<ll> v2 = P_convertion(A, v1); if (r == 1) { cout << ((v1[0] + v1[1] + v2[0]) % mod) << endl; } else { cout << ((v1[0] + v1[1]) % mod) << endl; } } return 0; }