結果

問題 No.1810 RGB Biscuits
ユーザー Nikita SkybytskyiNikita Skybytskyi
提出日時 2022-01-14 22:12:30
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
AC  
実行時間 28 ms / 2,000 ms
コード長 1,994 bytes
コンパイル時間 3,595 ms
コンパイル使用メモリ 136,324 KB
実行使用メモリ 4,388 KB
最終ジャッジ日時 2023-08-12 20:08:40
合計ジャッジ時間 4,110 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge9
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,388 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 27 ms
4,380 KB
testcase_07 AC 28 ms
4,376 KB
testcase_08 AC 27 ms
4,376 KB
testcase_09 AC 28 ms
4,380 KB
testcase_10 AC 3 ms
4,384 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 7 ms
4,380 KB
testcase_15 AC 3 ms
4,380 KB
testcase_16 AC 4 ms
4,380 KB
testcase_17 AC 16 ms
4,376 KB
testcase_18 AC 16 ms
4,380 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 5 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

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