結果

問題 No.1810 RGB Biscuits
ユーザー Nikita Skybytskyi
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
 * 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;
}
0