#713866 (C++17) No.1810 RGB Biscuits

• 問題: No.1810 RGB Biscuits
• ユーザー: polylogK
• 提出日時: 2021-11-06 21:06:29
• 言語: C++17 (gcc 13.2.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 20 ms / 2,000 ms
• コード長: 1,453 bytes
• コンパイル時間: 582 ms
• コンパイル使用メモリ: 58,364 KB
• 実行使用メモリ: 4,380 KB
• 最終ジャッジ日時: 2023-08-07 15:51:47
• 合計ジャッジ時間: 1,723 ms
• ジャッジサーバーID （参考情報）: judge12 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,380 KB
testcase_01	AC	2 ms; 4,376 KB
testcase_02	AC	2 ms; 4,380 KB
testcase_03	AC	1 ms; 4,376 KB
testcase_04	AC	2 ms; 4,380 KB
testcase_05	AC	18 ms; 4,380 KB
testcase_06	AC	19 ms; 4,376 KB
testcase_07	AC	20 ms; 4,380 KB
testcase_08	AC	19 ms; 4,380 KB
testcase_09	AC	19 ms; 4,376 KB
testcase_10	AC	13 ms; 4,376 KB
testcase_11	AC	2 ms; 4,376 KB
testcase_12	AC	2 ms; 4,380 KB
testcase_13	AC	2 ms; 4,380 KB
testcase_14	AC	4 ms; 4,376 KB
testcase_15	AC	2 ms; 4,380 KB
testcase_16	AC	2 ms; 4,376 KB
testcase_17	AC	10 ms; 4,376 KB
testcase_18	AC	10 ms; 4,376 KB
testcase_19	AC	1 ms; 4,376 KB
testcase_20	AC	1 ms; 4,380 KB
testcase_21	AC	3 ms; 4,376 KB

ソースコード

/*
	# Algorithm

	use matrix multiplication
	[[A, B, 1],
	 [1, 0, 0],
	 [0, 0, 0]]

	## Time Complexity

	O(NlogT)
*/

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

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

struct matrix_t {
	using i64 = long long;

	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;
}