結果
問題 |
No.3040 Aoiスコア
|
ユーザー |
![]() |
提出日時 | 2025-02-28 22:49:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 1,000 ms |
コード長 | 1,217 bytes |
コンパイル時間 | 4,240 ms |
コンパイル使用メモリ | 259,916 KB |
実行使用メモリ | 7,844 KB |
最終ジャッジ日時 | 2025-06-20 20:59:52 |
合計ジャッジ時間 | 4,625 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; #pragma GCC target("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define FASTIO cin.tie(0)->sync_with_stdio(0) using ll = long long; using mint = modint998244353; int main() { FASTIO; int N, M; string S; cin >> N >> M >> S; vector<vector<int>> G(N); for(int i = 0; i < M; ++i) { int a, b; cin >> a >> b; a--, b--; G[a].push_back(b); G[b].push_back(a); } int q = 0; for(int i = 0; i < N; ++i) { if(S[i] == '?') ++q; } vector<mint> pw(N + 1, 1); for(int i = 0; i < N; i++) { pw[i + 1] = pw[i] * 26; } mint ans; for(int i = 0; i < N; i++) { if(S[i] != 'o' && S[i] != '?') continue; mint a = 0, b = 0; int n = 0; for(int j : G[i]) { if(S[j] == 'a') a++; if(S[j] == 'i') b++; if(S[j] == '?') n++; } int q2 = q - n - (S[i] == '?'); if(n == 0) { ans += pw[q2] * a * b; }else if(n == 1) { ans += pw[q2] * (24 * a * b + (a + 1) * b + a * (b + 1)); }else { ans += pw[q2] * pw[n - 2] * (26 * a * (26 * b + n) + n * (26 * b + n - 1)); } } cout << ans.val() << endl; }