#746455 (C++17) No.1873 Bracket Swapping

提出ソース

結果

問題	No.1873 Bracket Swapping
ユーザー	yudedako
提出日時	2022-03-17 18:35:39
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	265 ms / 2,000 ms
コード長	5,911 bytes
コンパイル時間	1,654 ms
コンパイル使用メモリ	141,712 KB
実行使用メモリ	20,608 KB
最終ジャッジ日時	2024-04-09 03:36:11
合計ジャッジ時間	5,213 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	24 ms 6,948 KB
testcase_04	AC	10 ms 6,944 KB
testcase_05	AC	10 ms 6,948 KB
testcase_06	AC	107 ms 11,904 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	200 ms 19,200 KB
testcase_09	AC	202 ms 20,480 KB
testcase_10	AC	153 ms 16,128 KB
testcase_11	AC	3 ms 6,944 KB
testcase_12	AC	81 ms 10,496 KB
testcase_13	AC	66 ms 9,088 KB
testcase_14	AC	198 ms 18,560 KB
testcase_15	AC	42 ms 6,948 KB
testcase_16	AC	2 ms 6,944 KB
testcase_17	AC	105 ms 13,440 KB
testcase_18	AC	3 ms 6,944 KB
testcase_19	AC	7 ms 6,944 KB
testcase_20	AC	168 ms 16,640 KB
testcase_21	AC	3 ms 6,944 KB
testcase_22	AC	14 ms 6,948 KB
testcase_23	AC	265 ms 20,608 KB
testcase_24	AC	183 ms 20,480 KB
testcase_25	AC	209 ms 20,608 KB
testcase_26	AC	104 ms 13,568 KB
testcase_27	AC	148 ms 17,792 KB
testcase_28	AC	25 ms 20,224 KB
testcase_29	AC	2 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <queue>
#include <string>
#include <random>
#include <array>
#include <climits>
#include <map>
#include <cassert>
#include <stack>
#include <iomanip>
#include <cfloat>
#include <bitset>
#include <fstream>
#include <chrono>

constexpr int MOD = 998244353;

template<int MOD = 998244353>
class ModInt {
	long long int raw_value;
	static long long int inverse(const long long int value) {
		long long int
			x = value,
			y = MOD,
			a = 1,
			b = 0,
			c = 0,
			d = 1;
		while (y != 0) {
			const auto q = x / y;
			const auto e = a - c * q;
			const auto f = b - d * q;
			a = c;
			b = d;
			c = e;
			d = f;
			x = y;
			y = c * value - d * MOD;
		}
		assert(std::abs(x) == 1LL);
		return x == 1 ? a % MOD : -a % MOD;
	}
public:
	ModInt() : raw_value{ 0 } {};
	ModInt(const int value) : raw_value{ value } {};
	ModInt(const long long int value) : raw_value{ value % MOD } {};
	ModInt<MOD> operator+(const ModInt<MOD> right) const {
		return raw_value + right.raw_value;
	}
	ModInt<MOD>& operator+=(const ModInt<MOD> right) {
		return *this = *this + right;
	}
	ModInt<MOD> operator-(const ModInt<MOD> right) const {
		return raw_value - right.raw_value;
	}
	ModInt<MOD>& operator-=(const ModInt<MOD> right) {
		return *this = *this - right;
	}
	ModInt<MOD> operator*(const ModInt<MOD> right) const {
		return raw_value * right.raw_value;
	}
	ModInt<MOD>& operator*=(const ModInt<MOD> right) const {
		return *this = *this * right;
	}
	ModInt<MOD> operator/(const ModInt<MOD> right) const {
		return raw_value * inverse(right.raw_value);
	}
	ModInt<MOD> operator/=(const ModInt<MOD> right) {
		return *this = *this / right;
	}
	ModInt<MOD> pow(long long int exp) const {
		ModInt result(1), base{ *this };
		while (exp > 0) {
			if ((exp & 1) == 1) {
				result *= base;
			}
			base *= base;
			exp >>= 1;
		}
		return result;
	}
	long long int value() const { return (raw_value + MOD) % MOD; }
};
template<int MOD>
std::ostream& operator<<(std::ostream& os, const ModInt<MOD>& mint) {
	return os << (mint.value() + MOD) % MOD;
}
template<typename T>
class Matrix {
	std::vector<std::vector<T>> vec;
	int _row, _column;
public:
	int row() const { return _row; }
	int column() const { return _column; }
	static Matrix<T> E(const int size) {
		Matrix<T> result(size, size);
		for (auto i = 0; i < size; ++i) {
			result[i][i] = 1;
		}
		return result;
	}
	Matrix(const int row, const int column) : vec(row, std::vector<T>(column)), _row{ row }, _column{ column } {};
	Matrix(Matrix<T>&& other) = default;
	Matrix(const Matrix<T> & other) = default;
	Matrix<T>& operator=(Matrix<T> &&other) = default;
	Matrix<T>& operator=(const Matrix<T> & other) = default;
	const std::vector<T>& operator[](const int index) const {
		return vec[index];
	}
	std::vector<T>& operator[](const int index) {
		return vec[index];
	}
	Matrix<T> operator*(const Matrix<T>& right) const {
		const int row = this->row();
		const int mid = this->column();
		const int column = right.column();
		Matrix result(row, column);
		for (auto i = 0; i < row; ++i) {
			for (auto j = 0; j < column; ++j) {
				T value = vec[i][0] * right.vec[0][j];
				for (auto k = 1; k < mid; ++k) {
					value += vec[i][k] * right.vec[k][j];
				}
				result[i][j] = value;
			}
		}
		return result;
	}
	Matrix<T>& operator*=(const Matrix<T>& right) {
		return *this = *this * right;
	}
	Matrix<T> pow(long long int exp) const {
		auto result = Matrix<T>::E(row());
		auto base = *this;
		while (exp > 0) {
			if ((exp & 1) == 1) {
				result *= base;
			}
			base *= base;
			exp >>= 1;
		}
		return result;
	}
};
template<typename T>
std::ostream& operator<<(std::ostream& os, const Matrix<T>& matrix) {
	for (auto i = 0; i < matrix.row(); ++i) {
		os << '[';
		for (auto j = 0; j < matrix.column(); ++j) {
			if (j > 0) {
				os << ", ";
			}
			os << matrix[i][j];
		}
		os << "]\n";
	}
	return os;
}

Matrix<ModInt<MOD>> make_matrix(const int size) {
	const int half = size / 2;
	Matrix<ModInt<MOD>> result(half + 1, half + 1);
	for (auto i = 0; i <= half; ++i) {
		if (0 <= i - 1) {
			result[i][i - 1] = (half - i + 1) * (half - i + 1);
		}
		result[i][i] = (half - i) * (half - i - 1) + i * (i - 1) + 2 * (size - 2 * i) * i;
		if (i + 1 <= half) {
			result[i][i + 1] = (i + 1) * (i + 1);
		}
	}
	return result;
}

template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
	os << "[";
	for (auto i = 0; i < vec.size(); ++i) {
		if (i > 0) {
			os << ", ";
		}
		os << vec[i];
	}
	return os << "]";
}
int main() {
	std::string str; std::cin >> str;
	int k; std::cin >> k;
	const int size = str.size();
	const int half = size / 2;
	std::vector<std::vector<std::vector<ModInt<MOD>>>> memo(size + 1, std::vector<std::vector<ModInt<MOD>>>(half + 1, std::vector<ModInt<MOD>>(half + 1)));
	memo[0][0][0] = 1;
	for (auto i = 0; i < size; ++i) {
		const auto c = str[i];
		for (auto height = 0; height <= half; ++height) {
			for (auto to_right = 0; to_right <= half; ++to_right) {
				if (c == '(') {
					ModInt<MOD> pattern{ 0 };
					if (0 <= height - 1) {
						pattern += memo[i][height - 1][to_right];
					}
					if (height + 1 <= half && 0 < to_right) {
						pattern += memo[i][height + 1][to_right - 1];
					}
					memo[i + 1][height][to_right] = pattern;
				}
				else {
					ModInt<MOD> pattern{ 0 };
					if (height + 1 <= half) {
						pattern += memo[i][height + 1][to_right];
					}
					if (0 <= height - 1) {
						pattern += memo[i][height - 1][to_right];
					}
					memo[i + 1][height][to_right] = pattern;
				}
			}
		}
	}
	const auto matrix = make_matrix(size).pow(k);
	ModInt<MOD> result{ 0 };
	for (auto to_right = 0; to_right <= half; ++to_right) {
		result += matrix[0][to_right] * memo[size][0][to_right];
	}
	std::cout << result << '\n';
}

yukicoder

結果

テストケース

ソースコード