結果
| 問題 | No.3040 Aoiスコア |
| ユーザー |
 elphe
|
| 提出日時 | 2025-03-03 20:03:48 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,450 bytes |
| コンパイル時間 | 1,130 ms |
| コンパイル使用メモリ | 89,188 KB |
| 実行使用メモリ | 8,612 KB |
| 最終ジャッジ日時 | 2025-03-03 20:03:53 |
| 合計ジャッジ時間 | 4,861 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 9 WA * 14 TLE * 1 |
ソースコード
#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); elsereturn 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."); ifconstexpr (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; elsethis->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."); ifconstexpr (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."); ifconstexpr (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;}