結果

問題 No.3040 Aoiスコア
ユーザー Tatsu_mr
提出日時 2025-03-01 11:47:11
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 88 ms / 1,000 ms
コード長 1,666 bytes
コンパイル時間 2,845 ms
コンパイル使用メモリ 284,092 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-20 21:02:25
合計ジャッジ時間 4,027 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define For(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, n) For(i, 0, n)
#define rFor(i, a, b) for(int i = (a); i >= (b); i--)
#define ALL(v) (v).begin(), (v).end()
#define rALL(v) (v).rbegin(), (v).rend()

using lint = long long;
using ld = long double;

int INF = 2000000000;
lint LINF = 1000000000000000000;

struct SetupIo {
    SetupIo() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} setupio;

#include <atcoder/modint>
using mint = atcoder::modint998244353;

int main() {
    int n, m;
    string s;
    cin >> n >> m >> s;
    int cnt = 0;
    for (char c : s) {
        if (c == '?') {
            cnt++;
        }
    }
    vector<vector<int>> g(n);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        g[a].emplace_back(b);
        g[b].emplace_back(a);
    }
    vector<mint> pows(cnt + 1);
    pows[0] = 1;
    For(i, 1, cnt + 1) {
        pows[i] = pows[i - 1] * mint(26);
    }
    mint ans = 0;
    rep(v, n) {
        if (s[v] != 'o' && s[v] != '?') { 
            continue; 
        }
        for (int u : g[v]) {
            if (s[u] != 'a' && s[u] != '?') {
                continue;
            }
            for (int w : g[v]) {
                if (w == u) {
                    continue;
                }
                if (s[w] != 'i' && s[w] != '?') {
                    continue;
                }
                int cur = cnt - (s[u] == '?') - (s[v] == '?') - (s[w] == '?');
                ans += pows[cur];
            }
        }
    }
    cout << ans.val() << "\n";
}
0