結果

問題 No.1810 RGB Biscuits
ユーザー polylogKpolylogK
提出日時 2021-11-08 17:47:17
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,349 bytes
コンパイル時間 777 ms
コンパイル使用メモリ 58,292 KB
実行使用メモリ 13,440 KB
最終ジャッジ日時 2024-11-16 13:25:08
合計ジャッジ時間 52,878 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

/*
	WA: Overflow
*/

#include <stdio.h>
#include <vector>

constexpr int MOD = 1'000'000'007;

struct matrix_t {
	using i64 = int;

	std::vector<std::vector<i64>> matrix;

	matrix_t(): matrix(3, std::vector<i64>(3)) {}
	matrix_t(const std::vector<std::vector<i64>>& matrix): matrix(matrix) {}

	static matrix_t E() {
		return matrix_t({{1, 0, 0}, {0, 1, 0}, {0, 0, 1}});
	}

	std::vector<i64>& operator[](int k) { return matrix[k]; }

	inline matrix_t operator*(const matrix_t& r) const {
		matrix_t ret;
		for(size_t i = 0; i < 3; i++) {
			for(size_t j = 0; j < 3; j++) {
				for(size_t k = 0; k < 3; k++) {
					(ret[i][j] += matrix[i][k] * r.matrix[k][j]) %= MOD;
				}
			}
		}
		return std::move(ret);
	}

	inline matrix_t operator^=(i64 k) {
		matrix_t tmp = E();
		while(k) {
			if(k & 1) tmp = tmp * (*this);
			(*this) = (*this) * (*this);
			k >>= 1;
		}
		matrix.swap(tmp.matrix);
		return *this;
	}
};

int main() {
	int A, B, N; scanf("%d%d%d", &A, &B, &N);

	using i64 = long long;
	while(N--) {
		i64 T; scanf("%lld", &T);

		matrix_t matrix({{A, B, 1}, {1, 0, 0}, {0, 0, 0}});
		matrix ^= T / 2;

		if(T % 2) {
			matrix = matrix_t({{1, 0, 0}, {0, 1, 0}, {A, B, 1}}) * matrix;
		}

		int ans = 0;
		for(size_t i = 0; i < 3; i++) for(size_t j = 0; j < 2; j++) ans = (ans + matrix[i][j]) % MOD;
		printf("%d\n", ans);
	}
	return 0;
}
0