結果

問題 No.1810 RGB Biscuits
ユーザー polylogKpolylogK
提出日時 2021-11-06 21:06:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 34 ms / 2,000 ms
コード長 1,453 bytes
コンパイル時間 812 ms
コンパイル使用メモリ 56,832 KB
最終ジャッジ日時 2025-01-25 14:18:53
ジャッジサーバーID
（参考情報） 		judge8 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:58:27: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   58 |         int A, B, N; scanf("%d%d%d", &A, &B, &N);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:62:29: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   62 |                 i64 T; scanf("%lld", &T);
      |                        ~~~~~^~~~~~~~~~~~

ソースコード

diff # 

/*
	# 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;
}
0