結果

問題 No.1810 RGB Biscuits
コンテスト
ユーザー MasKoaTS
提出日時 2024-11-30 18:44:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 76 ms / 2,000 ms
コード長 1,813 bytes
コンパイル時間 1,999 ms
コンパイル使用メモリ 198,632 KB
最終ジャッジ日時 2025-02-26 09:42:46
ジャッジサーバーID
（参考情報） 		judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/modint>
#define INF 4611686018427387903ll
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint1000000007;

struct Matrix22 {
    mint v11, v12, v21, v22;

    Matrix22(void){
        this->v11 = 1;
        this->v12 = 0;
        this->v21 = 0;
        this->v22 = 1;
    }

	Matrix22(mint v11, mint v12, mint v21, mint v22) {
		this->v11 = v11;
        this->v12 = v12;
        this->v21 = v21;
        this->v22 = v22;
	}

	Matrix22 operator*(const Matrix22 other) const {
		return Matrix22((this->v11 * other.v11) + (this->v12 * other.v21),
            (this->v11 * other.v12) + (this->v12 * other.v22),
            (this->v21 * other.v11) + (this->v22 * other.v21),
            (this->v21 * other.v12) + (this->v22 * other.v22));
	}

    pair<mint, mint> operator*(const pair<mint, mint> other) const {
        return pair<mint, mint>((this->v11 * other.first) + (this->v12 * other.second),
            (this->v21 * other.first) + (this->v22 * other.second));
    }

    Matrix22 pow(ll n){
        Matrix22 ret = Matrix22();
        Matrix22 A = *this;
        while(n){
            if(n & 1){
                ret = A * ret;
            }
            A = A * A;
            n >>= 1;
        }
        return ret;
    }
};


int main(){
    ll a, b;    cin >> a >> b;
    ll n;   cin >> n;

    Matrix22 A(a, b, 1, 0);
    pair<mint, mint> v(1, 1);
    for(int i = 0; i < n; ++i){
        ll t;   cin >> t;
        ll d = t / 2, r = t % 2;
        pair<mint, mint> v1 = A.pow(d) * v;
        pair<mint, mint> v2 = A * v1;
        mint ans = 0;
        if(r == 1){
            ans = v1.first + v1.second + v2.first;
        }
        else{
            ans = v1.first + v1.second;
        }
        cout << ans.val() << endl;
    }
}
0