結果

問題 No.3040 Aoiスコア
ユーザー Ponzu
提出日時 2025-02-28 23:01:33
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,276 bytes
コンパイル時間 864 ms
コンパイル使用メモリ 92,076 KB
実行使用メモリ 8,236 KB
最終ジャッジ日時 2025-02-28 23:01:38
合計ジャッジ時間 1,783 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<vector>
#include<cassert>
using namespace std;
long long modpow(long long a, long long n, long long m)
{
    assert(m>=1);
    if(a==0) return 0LL;
    long long res = 1;
    while(n > 0)
    {
        if(n&1) res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
}
const long long MOD = 998244353;
int main()
{
    int N,M;string S;
    cin >> N >> M >> S;
    long long q_count = 0;
    for(char c : S) if(c=='?') q_count++;
    vector<vector<int>> G(N);
    for(int i=0;i<M;++i)
    {
        int u,v;
        cin >> u >> v;
        --u,--v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    string check = "ai?";
    long long ans = 0;
    for(int u=0;u<N;++u)
    {
        if(S[u] == 'o' || S[u] == '?')
        {
            vector<int> vertexes;
            string str = "";
            vector<long long> count(3);
            for(int v : G[u])
            {
                vertexes.emplace_back(v);
                for(int i=0;i<3;++i) if(check[i] == S[v]) count[i]++;
            }
            long long q = S[u]=='?' ? q_count-1 : q_count;
            ans += count[0] * count[1] % MOD * modpow(26,q,MOD) % MOD;
            ans %= MOD;
            ans += count[0] * count[2] % MOD * modpow(26,q,MOD) % MOD;
            ans %= MOD;
            ans += count[1] * count[2] % MOD * modpow(26,q,MOD) % MOD;
            ans %= MOD;
            ans += count[2]*(count[2]-1) % MOD * modpow(26,q-count[2],MOD) % MOD;
            ans %= MOD;
        }
    }
    cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0