結果

問題 No.3040 Aoiスコア
ユーザー 回転
提出日時 2025-02-28 23:57:19
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,497 bytes
コンパイル時間 3,068 ms
コンパイル使用メモリ 286,396 KB
実行使用メモリ 16,064 KB
最終ジャッジ日時 2025-06-20 21:02:00
合計ジャッジ時間 6,017 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23 TLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

int N, M;
string S;
vector<vector<int>> edge;
int all_hatena;
ll hatena_count;
unordered_set<int> visited;

ll power(ll base, ll exp, ll mod) {
    ll res = 1;
    while (exp > 0) {
        if (exp % 2 == 1) res = res * base % mod;
        base = base * base % mod;
        exp /= 2;
    }
    return res;
}

ll f(int n, int depth) {
    if (depth == 3) return power(26, all_hatena - hatena_count, MOD);
    ll ret = 0;
    for (int i : edge[n]) {
        if (visited.count(i)) continue;
        if (S[i] != '?' && S[i] != "aoi"[depth]) continue;
        if (S[i] == '?') hatena_count++;
        visited.insert(i);
        ret = (ret + f(i, depth + 1)) % MOD;
        visited.erase(i);
        if (S[i] == '?') hatena_count--;
    }
    return ret % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> M >> S;
    edge.resize(N);
    
    all_hatena = count(S.begin(), S.end(), '?');
    
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        if (S[i] == 'a' || S[i] == '?') {
            hatena_count = (S[i] == '?') ? 1 : 0;
            visited.clear();
            visited.insert(i);
            ans = (ans + f(i, 1)) % MOD;
        }
    }
    
    cout << ans << "\n";
    return 0;
}
0