結果

問題 No.3040 Aoiスコア
コンテスト
ユーザー elphe
提出日時 2025-03-03 20:03:48
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 9,450 bytes
コンパイル時間 740 ms
コンパイル使用メモリ 89,332 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-06-20 21:03:09
合計ジャッジ時間 6,589 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 WA * 14 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using namespace std;

template<unsigned int MOD> class mod_int
{
private:
	unsigned int value = 0;
	inline 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;
	}
	inline 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:
	inline 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); }

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

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

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

	inline constexpr bool operator==(const mod_int<MOD> other) const noexcept { return this->value == other.value; }
	inline constexpr bool operator!=(const mod_int<MOD> other) const noexcept { return this->value != other.value; }
	inline constexpr bool operator<(const mod_int<MOD> other) const noexcept { return this->value < other.value; }
	inline constexpr bool operator<=(const mod_int<MOD> other) const noexcept { return this->value <= other.value; }
	inline constexpr bool operator>(const mod_int<MOD> other) const noexcept { return this->value > other.value; }
	inline 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; }

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

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

		return ans;
	}

	inline static constexpr mod_int<MOD> pow_mod(mod_int<MOD> base, unsigned long long times) noexcept
	{
		if (MOD == 1) return 0;
		mod_int<MOD> ans = 1;
		for (; times != 0; times >>= 1, base *= base)
			if (times & 1) ans.value *= base;

		return ans;
	}
};

inline constexpr bool is_matching(const char c, const char pattern = '?') noexcept
{
	return (c == '?' || c == pattern);
}

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

	uint32_t N, M, i, j;
	string S;
	cin >> N >> M;
	S.reserve(N), cin >> S;
	vector<uint32_t> A(M), B(M);
	for (i = 0; i != M; ++i) cin >> A[i] >> B[i];

	uint32_t count_ambiguous = 0;
	for (i = 0; i != M; ++i) --A[i], --B[i];
	for (i = 0; i != N; ++i)
		if (S[i] == '?') ++count_ambiguous;

	mod_int<998244353> ans = 0;
	for (i = 0; i != M; ++i)
		for (j = 0; j != M; ++j)
			if (i != j)
			{
				if (B[i] == A[j] && is_matching(S[A[i]], 'a') && is_matching(S[B[i]], 'o') && is_matching(S[B[j]], 'i'))
					ans += mod_int<998244353>::pow_mod(mod_int<998244353>(26), count_ambiguous - (S[A[i]] == '?') - (S[B[i]] == '?') - (S[B[j]] == '?'));
				else if (A[i] == B[j] && is_matching(S[B[i]], 'a') && is_matching(S[A[i]], 'o') && is_matching(S[A[j]], 'i'))
					ans += mod_int<998244353>::pow_mod(mod_int<998244353>(26), count_ambiguous - (S[B[i]] == '?') - (S[A[i]] == '?') - (S[A[j]] == '?'));
				else if (A[i] == A[j] && is_matching(S[B[i]], 'a') && is_matching(S[A[i]], 'o') && is_matching(S[B[j]], 'i'))
					ans += mod_int<998244353>::pow_mod(mod_int<998244353>(26), count_ambiguous - (S[B[i]] == '?') - (S[A[i]] == '?') - (S[B[j]] == '?'));
				else if (B[i] == B[j] && is_matching(S[A[i]], 'a') && is_matching(S[B[i]], 'o') && is_matching(S[A[j]], 'i'))
					ans += mod_int<998244353>::pow_mod(mod_int<998244353>(26), count_ambiguous - (S[A[i]] == '?') - (S[B[i]] == '?') - (S[A[j]] == '?'));
			}

	cout << ans << '\n';
	return 0;
}
0