結果

問題 No.1810 RGB Biscuits
ユーザー take000take000
提出日時 2023-03-13 11:23:23
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 27 ms / 2,000 ms
コード長 2,345 bytes
コンパイル時間 4,798 ms
コンパイル使用メモリ 274,316 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-18 10:55:50
合計ジャッジ時間 6,168 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <atcoder/all>
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
typedef long long ll;
using namespace atcoder;
using namespace std;
using mint = modint1000000007;

template <typename T>
struct Matrix {
    vector<vector<T>> A;

    Matrix() {}
    Matrix(int H, int W) : A(H, vector<T>(W, 0)) {}

    inline const vector<T> &operator[](int i) const { return A.at(i); }
    inline vector<T> &operator[](int i) { return A.at(i); }

    int get_height() const { return A.size(); }
    int get_width() const { return A[0].size(); }

    inline T add(T a, T b) { return a + b; }
    inline T mul(T a, T b) { return a * b; }
    T e = 1;

    Matrix &operator+=(const Matrix &A) {
        int H = get_height(), W = get_width();
        assert(H == A.get_height() && W == A.get_width());
        rep(i, H) rep(j, W)(*this)[i][j] = add((*this)[i][j], A[i][j]);
        return (*this);
    }

    Matrix &operator*=(const Matrix &B) {
        int H = get_height(), W = B.get_width(), Z = get_width();
        assert(Z == B.get_height());

        vector<vector<T>> C(H, vector<T>(W));
        rep(i, H) rep(j, W) rep(k, Z) C[i][j] = add(C[i][j], mul((*this)[i][k], B[k][j]));
        (*this).A = C;
        return (*this);
    }

    Matrix &operator^=(ll k) {
        int N = get_height();
        Matrix B(N, N);
        rep(i, N) B.A[i][i] = e;

        while (k > 0) {
            if (k & 1) B *= (*this);
            (*this) *= (*this);
            k >>= 1LL;
        }
        (*this) = B;
        return (*this);
    }

    Matrix operator+(const Matrix &B) const { return Matrix(*this) += B; }
    Matrix operator*(const Matrix &B) const { return Matrix(*this) *= B; }
    Matrix operator^(ll k) const { return Matrix(*this) ^= k; }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);

    ll A, B;
    int N;
    cin >> A >> B >> N;

    Matrix<mint> MA(3, 3), MB(3, 3);
    MA.A = {{1, A, B}, {0, 1, 0}, {0, 0, 1}};
    MB.A = {{0, 0, 0}, {1, 0, 0}, {0, 1, 0}};
    Matrix<mint> MC = MB * MA;

    rep(i, N) {
        ll T;
        cin >> T;

        Matrix<mint> init(3, 1);
        init.A = {{0}, {1}, {1}};
        Matrix<mint> M = (MC ^ (T / 2)) * init;

        mint ans = M[1][0] + M[2][0];
        if (T % 2 == 1) ans += M[1][0] * A + M[2][0] * B;
        cout << ans.val() << "\n";
    }

    return 0;
}
0