結果

問題 No.1810 RGB Biscuits
コンテスト
ユーザー take000
提出日時 2023-03-13 11:23:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 25 ms / 2,000 ms
コード長 2,345 bytes
コンパイル時間 4,838 ms
コンパイル使用メモリ 265,064 KB
最終ジャッジ日時 2025-02-11 10:49:58
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

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