結果

問題 No.1810 RGB Biscuits
ユーザー MasKoaTSMasKoaTS
提出日時 2024-11-30 18:44:59
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 1,813 bytes
コンパイル時間 2,266 ms
コンパイル使用メモリ 204,892 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-30 18:45:03
合計ジャッジ時間 3,202 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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