#1021972 (C++17) No.2926 Botaoshi

提出ソース
結果

問題	No.2926 Botaoshi
コンテスト
ユーザー	elphe
提出日時	2024-10-23 18:12:12
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	5 ms / 2,000 ms
コード長	8,617 bytes
コンパイル時間	920 ms
コンパイル使用メモリ	72,816 KB
最終ジャッジ日時	2025-02-24 22:27:48
ジャッジサーバーID （参考情報）	judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 4
other	AC * 42
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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;
}
yukicoder

結果

ソースコード
