結果

問題 No.3040 Aoiスコア
ユーザー detteiuu
提出日時 2025-02-28 21:47:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 101 ms / 1,000 ms
コード長 1,155 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 82,416 KB
実行使用メモリ 77,648 KB
最終ジャッジ日時 2025-06-20 20:56:18
合計ジャッジ時間 2,731 ms
ジャッジサーバーID
(参考情報)
judge2 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #

from math import comb

N, M = map(int, input().split())
S = input()
G = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    G[u-1].append(v-1)
    G[v-1].append(u-1)

MOD = 998244353

def inverse(n, d):
    return n * pow(d, -1, MOD) % MOD

C = S.count("?")
B = [pow(26, C, MOD)]
for _ in range(3):
    B.append(B[-1]*inverse(1, 26)%MOD)
ans = 0
for n in range(N):
    if S[n].isalpha() and S[n] != "o":
        continue
    a = 0
    i = 0
    q = 0
    for v in G[n]:
        if S[v] == "a":
            a += 1
        elif S[v] == "i":
            i += 1
        elif S[v] == "?":
            q += 1
    if S[n] == "o":
        ans += a*i%MOD*B[0]%MOD
        ans %= MOD
        ans += a*q%MOD*B[1]%MOD
        ans %= MOD
        ans += q*i%MOD*B[1]%MOD
        ans %= MOD
        if 2 <= q:
            ans += comb(q, 2)%MOD*B[2]*2%MOD
            ans %= MOD
    else:
        ans += a*i%MOD*B[1]%MOD
        ans %= MOD
        ans += a*q%MOD*B[2]%MOD
        ans %= MOD
        ans += q*i%MOD*B[2]%MOD
        ans %= MOD
        if 2 <= q:
            ans += comb(q, 2)%MOD*B[3]*2%MOD
            ans %= MOD

print(ans)
0