結果
問題 | No.3040 Aoiスコア |
ユーザー |
![]() |
提出日時 | 2025-01-06 21:43:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,736 bytes |
コンパイル時間 | 2,297 ms |
コンパイル使用メモリ | 200,556 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-06-20 20:54:36 |
合計ジャッジ時間 | 5,357 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 TLE * 1 -- * 2 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; ll modpow(ll b, ll exp, ll mod) { if (exp == 0) return 1LL; if (exp == 1) return b % mod; ll res = modpow(b, exp / 2, mod) % mod; res *= res; res %= mod; if (exp % 2 == 1) { res *= b % mod; res %= mod; } return res; } int main() { int N, M; cin >> N >> M; string S; cin >> S; assert(1 <= N && N <= 6000); assert(0 <= M && M <= 6000); assert(S.size() == N); const ll MOD = 998244353LL; vector<vector<int>> g(N, vector<int>()); for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; assert(1 <= a && a <= N); assert(1 <= b && b <= N); assert(a < b); a--; b--; g[a].push_back(b); g[b].push_back(a); } ll q = 0; for (int i = 0; i < N; i++) { if (S[i] == '?') { q++; } } ll ans = 0; for (int i = 0; i < N; i++) { vector<int>& n = g[i]; if (S[i] == 'o' || S[i] == '?') { for (int j = 0; j < n.size(); j++) { for (int k = 0; k < n.size(); k++) { if (j == k) continue; ll c = 0; if (S[n[j]] == '?') c++; else if (S[n[j]] != 'a') continue; if (S[n[k]] == '?') c++; else if (S[n[k]] != 'i') continue; if (S[i] == '?') c++; ans += modpow(26, q - c, MOD); ans %= MOD; } } } } cout << ans << endl; }