結果

問題 No.2926 Botaoshi
ユーザー elpheelphe
提出日時 2024-10-23 18:12:12
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 8,617 bytes
コンパイル時間 890 ms
コンパイル使用メモリ 74,864 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-23 18:12:16
合計ジャッジ時間 3,595 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 2 ms
6,820 KB
testcase_07 AC 1 ms
6,816 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 2 ms
6,820 KB
testcase_10 AC 2 ms
6,816 KB
testcase_11 AC 2 ms
6,816 KB
testcase_12 AC 5 ms
6,816 KB
testcase_13 AC 5 ms
6,820 KB
testcase_14 AC 5 ms
6,816 KB
testcase_15 AC 2 ms
6,820 KB
testcase_16 AC 4 ms
6,816 KB
testcase_17 AC 4 ms
6,816 KB
testcase_18 AC 2 ms
6,816 KB
testcase_19 AC 4 ms
6,820 KB
testcase_20 AC 2 ms
6,816 KB
testcase_21 AC 3 ms
6,816 KB
testcase_22 AC 4 ms
6,816 KB
testcase_23 AC 2 ms
6,816 KB
testcase_24 AC 4 ms
6,816 KB
testcase_25 AC 2 ms
6,816 KB
testcase_26 AC 5 ms
6,816 KB
testcase_27 AC 3 ms
6,816 KB
testcase_28 AC 2 ms
6,820 KB
testcase_29 AC 2 ms
6,820 KB
testcase_30 AC 3 ms
6,820 KB
testcase_31 AC 2 ms
6,816 KB
testcase_32 AC 3 ms
6,820 KB
testcase_33 AC 4 ms
6,816 KB
testcase_34 AC 4 ms
6,820 KB
testcase_35 AC 2 ms
6,816 KB
testcase_36 AC 5 ms
6,816 KB
testcase_37 AC 5 ms
6,816 KB
testcase_38 AC 5 ms
6,816 KB
testcase_39 AC 5 ms
6,816 KB
testcase_40 AC 5 ms
6,820 KB
testcase_41 AC 4 ms
6,816 KB
testcase_42 AC 5 ms
6,820 KB
testcase_43 AC 5 ms
6,816 KB
testcase_44 AC 4 ms
6,820 KB
testcase_45 AC 5 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdint>
#include <vector>

using namespace std;

template<unsigned int MOD> class mod_int
{
private:
	unsigned int value = 0;
	constexpr static bool is_prime(const unsigned int arg) noexcept
	{
		for (unsigned int i = 2; i * i <= arg; ++i)
			if (arg % i == 0) return false;
		return true;
	}
	constexpr static unsigned int pow_mod(unsigned int a, size_t b) noexcept
	{
		if (MOD == 1) return 0;
		unsigned int ans = 1;
		a %= MOD;
		for (; b != 0; b >>= 1, a = static_cast<unsigned long long>(a) * a % MOD)
			if (b & 1) ans = ans * static_cast<unsigned long long>(a) % MOD;

		return ans;
	}

public:
	constexpr mod_int() noexcept { static_assert(MOD != 0, "0 cannot be set as \'MOD.\'"); }
	template<typename T> constexpr mod_int(const T arg) noexcept { static_assert(MOD != 0, "0 cannot be set as \'MOD.\'"); value = (unsigned int)(arg % MOD); }

	constexpr mod_int<MOD> operator+(const mod_int<MOD> other) const noexcept { return mod_int(this->value >= MOD - other.value ? this->value - (MOD - other.value) : this->value + other.value); }
	constexpr mod_int<MOD> operator-(const mod_int<MOD> other) const noexcept { return mod_int(this->value >= other.value ? this->value - other.value : MOD - (other.value - this->value)); }
	constexpr mod_int<MOD> operator*(const mod_int<MOD> other) const noexcept { if constexpr (MOD >= (1u << 16)) return mod_int(static_cast<unsigned long long>(this->value) * other.value % MOD); else return mod_int(this->value * other.value % MOD); }
	constexpr mod_int<MOD> operator/(const mod_int<MOD> other) const noexcept { static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) return mod_int(static_cast<unsigned long long>(this->value) * pow_mod(other.value, MOD - 2) % MOD); else return mod_int(this->value * pow_mod(other.value, MOD - 2) % MOD); }
	template<typename T> constexpr mod_int<MOD> operator+(T arg) const noexcept { arg %= MOD; return mod_int(value >= MOD - static_cast<unsigned int>(arg) ? value - (MOD - static_cast<unsigned int>(arg)) : value + static_cast<unsigned int>(arg)); }
	template<typename T> constexpr mod_int<MOD> operator-(T arg) const noexcept { arg %= MOD; return mod_int(value >= static_cast<unsigned int>(arg) ? value - static_cast<unsigned int>(arg) : MOD - (static_cast<unsigned int>(arg) - value)); }
	template<typename T> constexpr mod_int<MOD> operator*(T arg) const noexcept { if constexpr (MOD >= (1u << 16)) return mod_int(static_cast<unsigned long long>(value) * (arg % MOD) % MOD); else return mod_int(value * static_cast<unsigned int>(arg % MOD) % MOD); }
	template<typename T> constexpr mod_int<MOD> operator/(T arg) const noexcept { static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) return mod_int(static_cast<unsigned long long>(value) * pow_mod(static_cast<unsigned int>(arg % MOD), MOD - 2) % MOD); else return mod_int(value * pow_mod(static_cast<unsigned int>(arg % MOD), MOD - 2) % MOD); }

	constexpr mod_int<MOD>& operator+=(const mod_int<MOD> other) noexcept { if (this->value >= MOD - other.value) this->value -= (MOD - other.value); else this->value += other.value; return *this; }
	constexpr mod_int<MOD>& operator-=(const mod_int<MOD> other) noexcept { if (this->value >= other.value) this->value -= other.value; else this->value += (MOD - other.value); return *this; }
	constexpr mod_int<MOD>& operator*=(const mod_int<MOD> other) noexcept { if constexpr (MOD >= (1u << 16)) this->value = static_cast<unsigned long long>(this->value) * other.value % MOD; else this->value = this->value * other.value % MOD; return *this; }
	constexpr mod_int<MOD>& operator/=(const mod_int<MOD> other) noexcept { static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) this->value = static_cast<unsigned long long>(this->value) * pow_mod(other.value, MOD - 2) % MOD; else this->value = this->value * pow_mod(other.value, MOD - 2) % MOD; return *this; }
	template<typename T> constexpr mod_int<MOD>& operator+=(T arg) noexcept { arg %= MOD; if (value >= MOD - arg) value -= (MOD - arg); else value += arg; return *this; }
	template<typename T> constexpr mod_int<MOD>& operator-=(T arg) noexcept { arg %= MOD; if (value >= arg) value -= arg; else value += (MOD - arg); return *this; }
	template<typename T> constexpr mod_int<MOD>& operator*=(T arg) noexcept { if constexpr (MOD >= (1u << 16)) value = static_cast<unsigned long long>(value) * (arg % MOD) % MOD; else value = value * (arg % MOD) % MOD; return *this; }
	template<typename T> constexpr mod_int<MOD>& operator/=(T arg) noexcept { static_assert(is_prime(MOD), "\'MOD\' is not a prime number."); if constexpr (MOD >= (1u << 16)) value = static_cast<unsigned long long>(value) * pow_mod(static_cast<unsigned int>(arg % MOD), MOD - 2) % MOD; else value = value * pow_mod(static_cast<unsigned int>(arg % MOD), MOD - 2) % MOD; return *this; }

	constexpr mod_int<MOD>& operator++() noexcept { if (value + 1 == MOD) value = 0; else ++value; return *this; }
	constexpr mod_int<MOD> operator++(int) noexcept { const auto temp = value; if (value + 1 == MOD) value = 0; else ++value; return mod_int<MOD>(temp); }
	constexpr mod_int<MOD>& operator--() noexcept { if (value == 0) value = MOD - 1; else --value; return *this; }
	constexpr mod_int<MOD> operator--(int) noexcept { const auto temp = value; if (value == 0) value = MOD - 1; else --value; return *this; }

	constexpr bool operator==(const mod_int<MOD> other) const noexcept { return this->value == other.value; }
	constexpr bool operator!=(const mod_int<MOD> other) const noexcept { return this->value != other.value; }
	constexpr bool operator<(const mod_int<MOD> other) const noexcept { return this->value < other.value; }
	constexpr bool operator<=(const mod_int<MOD> other) const noexcept { return this->value <= other.value; }
	constexpr bool operator>(const mod_int<MOD> other) const noexcept { return this->value > other.value; }
	constexpr bool operator>=(const mod_int<MOD> other) const noexcept { return this->value >= other.value; }
	template<typename T> constexpr bool operator==(const T arg) const noexcept { static_assert(is_integral<T>::value, "T is not an integral type."); return value == arg; }
	template<typename T> constexpr bool operator!=(const T arg) const noexcept { static_assert(is_integral<T>::value, "T is not an integral type."); return value != arg; }
	template<typename T> constexpr bool operator<(const T arg) const noexcept { static_assert(is_integral<T>::value, "T is not an integral type."); return value < arg; }
	template<typename T> constexpr bool operator<=(const T arg) const noexcept { static_assert(is_integral<T>::value, "T is not an integral type."); return value <= arg; }
	template<typename T> constexpr bool operator>(const T arg) const noexcept { static_assert(is_integral<T>::value, "T is not an integral type."); return value > arg; }
	template<typename T> constexpr bool operator>=(const T arg) const noexcept { static_assert(is_integral<T>::value, "T is not an integral type."); return value >= arg; }

	operator unsigned int() const noexcept { return this->value; }

	constexpr mod_int<MOD> pow_mod(unsigned long long times)
	{
		if (MOD == 1) return 0;
		mod_int<MOD> ans = 1;
		unsigned int a = this->value;
		for (; times != 0; times >>= 1, a = static_cast<unsigned long long>(a) * a % MOD)
			if (times & 1) ans.value = static_cast<unsigned long long>(ans.value) * a % MOD;

		return ans;
	}
};

int main()
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	uint32_t N, i;
	cin >> N;
	string S;
	S.reserve(N), cin >> S;

	mod_int<998244353> dp[2][3];
	switch (S[0])
	{
	case 'L':
		dp[1][0] = 1, dp[1][1] = dp[1][2] = 0;
		break;

	case 'R':
		dp[1][1] = 1, dp[1][0] = dp[1][2] = 0;
		break;

	case 'U':
		dp[1][2] = 1, dp[1][0] = dp[1][1] = 0;
		break;

	case '.':
		dp[1][0] = dp[1][1] = dp[1][2] = 1;
		break;
	}

	for (i = 1; i != N; ++i)
	{
		switch (S[i])
		{
		case 'L':
			dp[(i & 1) ^ 1][0] = dp[i & 1][0] + dp[i & 1][2];
			dp[(i & 1) ^ 1][1] = dp[(i & 1) ^ 1][2] = 0;
			break;

		case 'R':
			dp[(i & 1) ^ 1][1] = dp[i & 1][0] + dp[i & 1][1] + dp[i & 1][2];
			dp[(i & 1) ^ 1][0] = dp[(i & 1) ^ 1][2] = 0;
			break;

		case 'U':
			dp[(i & 1) ^ 1][2] = dp[i & 1][0] + dp[i & 1][1] + dp[i & 1][2];
			dp[(i & 1) ^ 1][0] = dp[(i & 1) ^ 1][1] = 0;
			break;

		case '.':
			dp[(i & 1) ^ 1][0] = dp[i & 1][0] + dp[i & 1][2];
			dp[(i & 1) ^ 1][1] = dp[(i & 1) ^ 1][2] = dp[i & 1][0] + dp[i & 1][1] + dp[i & 1][2];
			break;
		}
	}

	cout << dp[N & 1][0] + dp[N & 1][1] + dp[N & 1][2] << '\n';
	return 0;
}
0