結果
問題 |
No.3040 Aoiスコア
|
ユーザー |
![]() |
提出日時 | 2025-02-28 22:00:29 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 96 ms / 1,000 ms |
コード長 | 5,624 bytes |
コンパイル時間 | 3,159 ms |
コンパイル使用メモリ | 326,316 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-06-20 20:57:44 |
合計ジャッジ時間 | 4,037 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#pragma region header #include <immintrin.h> #include <algorithm> #include <array> #include <bitset> #include <cassert> #include <cctype> #include <cfenv> #include <cfloat> #include <chrono> #include <cinttypes> #include <climits> #include <cmath> #include <complex> #include <cstdarg> #include <cstddef> #include <cstdint> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <functional> #include <initializer_list> #include <iomanip> #include <ios> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <random> #include <set> #include <sstream> #include <stack> #include <streambuf> #include <string> #include <tuple> #include <type_traits> #include <typeinfo> #include <unordered_map> #include <unordered_set> #include <utility> #include <vector> using namespace std; struct Init{Init(){std::cin.tie(0); ios::sync_with_stdio(false); cout << setprecision(20) << fixed;}} init; using ll = long long; using ull = unsigned long long; using ld = long double; #define all(x) begin((x)), end((x)) #define pb push_back #define mp make_pair #define mt make_tuple #define uq(v) v.erase(unique(begin(v), end(v)), end(v)) template<class T> using pq = priority_queue<T>; template<class T> using pq_g = priority_queue<T, vector<T>, greater<T>>; template<class T> bool chmax(T &a, const T &b){if(a < b){a = b; return 1; } return 0;} template<class T> bool chmin(T &a, const T &b){if(a > b){a = b; return 1; } return 0;} constexpr ll INF = 2e18; constexpr int inf = 1e9; constexpr ld eps = 1e-15; constexpr int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1}; constexpr int dy[8] = {0, 1 ,0, -1, 1, -1, 1, -1}; #pragma endregion header template <uint32_t mod_, bool fast = false> struct MontgomeryModInt { private: using mint = MontgomeryModInt; using i32 = int32_t; using i64 = int64_t; using u32 = uint32_t; using u64 = uint64_t; static constexpr u32 get_r() { u32 ret = mod_; for (i32 i = 0; i < 4; i++) ret *= 2 - mod_ * ret; return ret; } static constexpr u32 r = get_r(); static constexpr u32 n2 = -u64(mod_) % mod_; static_assert(r * mod_ == 1, "invalid, r * mod != 1"); static_assert(mod_ < (1 << 30), "invalid, mod >= 2 ^ 30"); static_assert((mod_ & 1) == 1, "invalid, mod % 2 == 0"); u32 x; public: MontgomeryModInt() : x{} {} MontgomeryModInt(const i64 &a): x(reduce(u64(fast ? a : (a % mod() + mod())) * n2)) {} static constexpr u32 reduce(const u64 &b) { return u32(b >> 32) + mod() - u32((u64(u32(b) * r) * mod()) >> 32); } mint &operator+=(const mint &p) { if (i32(x += p.x - 2 * mod()) < 0) x += 2 * mod(); return *this; } mint &operator-=(const mint &p) { if (i32(x -= p.x) < 0) x += 2 * mod(); return *this; } mint &operator*=(const mint &p) { x = reduce(u64(x) * p.x); return *this; } mint &operator/=(const mint &p) { *this *= p.inv(); return *this; } mint operator-() const { return mint() - *this; } mint operator+(const mint &p) const { return mint(*this) += p; } mint operator-(const mint &p) const { return mint(*this) -= p; } mint operator*(const mint &p) const { return mint(*this) *= p; } mint operator/(const mint &p) const { return mint(*this) /= p; } bool operator==(const mint &p) const { return (x >= mod() ? x - mod() : x) == (p.x >= mod() ? p.x - mod() : p.x); } bool operator!=(const mint &p) const { return (x >= mod() ? x - mod() : x) != (p.x >= mod() ? p.x - mod() : p.x); } u32 val() const { u32 ret = reduce(x); return ret >= mod() ? ret - mod() : ret; } mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } mint inv() const { return pow(mod() - 2); } friend ostream &operator<<(ostream &os, const mint &p) { return os << p.val(); } friend istream &operator>>(istream &is, mint &a) { i64 t; is >> t; a = mint(t); return is; } static constexpr u32 mod() { return mod_; } }; template <uint32_t mod> using modint = MontgomeryModInt<mod>; using mint = modint<998244353>; using modint1000000007 = modint<1000000007>; int main(){ int N, M; cin >> N >> M; string S; cin >> S; vector<vector<int>> H(N); for(int i = 0; i < M; ++i){ int A, B; cin >> A >> B; H[--A].pb(--B); H[B].pb(A); } int cnt = 0; for(int i = 0; i < N; ++i) if(S[i] == '?') ++cnt; mint tei = 1; for(int i = 0; i < cnt; ++i) tei *= 26; vector<mint> k = {1, (mint)1 / 26, (mint)1 / (26 * 26), (mint)1 / (26 * 26 * 26)}; mint ans = 0; for(int i = 0; i < N; ++i){ int num = 0; if(S[i] == '?') ++num; else if(S[i] != 'a') continue; for(auto u: H[i]){ if(S[u] == '?') ++num; else if(S[u] != 'o') continue; for(auto v: H[u]){ if(S[v] == '?') ++num; else if(S[v] != 'i') continue; if(v == i){ if(S[v] == '?') --num; continue; } ans += tei * k[num]; if(S[v] == '?') --num; } if(S[u] == '?') --num; } } cout << ans << "\n"; }