結果

問題 No.3040 Aoiスコア
コンテスト
ユーザー bfs84
提出日時 2025-02-28 23:17:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 89 ms / 1,000 ms
コード長 2,149 bytes
コンパイル時間 222 ms
コンパイル使用メモリ 82,100 KB
実行使用メモリ 78,056 KB
最終ジャッジ日時 2025-06-20 21:01:23
合計ジャッジ時間 2,512 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
import sys

def main():
    data = sys.stdin.read().strip().splitlines()
    data = [line.strip() for line in data if line.strip()]
    if not data:
        return

    # 1行目：N, M の取得
    N, M = map(int, data[0].split())
    # 2行目：S の文字リスト化
    S = list(data[1])
    
    # 3行目以降：辺の情報（頂点番号は1-indexed → 0-indexedに変換）
    A = []
    B = []
    for i in range(M):
        a, b = map(int, data[i+2].split())
        A.append(a)
        B.append(b)
    
    mod = 998244353
    # グラフの構築
    G = [[] for _ in range(N)]
    for i in range(M):
        a = A[i] - 1
        b = B[i] - 1
        G[a].append(b)
        G[b].append(a)
    
    # S に含まれる "?" の総数
    total_q = S.count("?")
    
    def calc(can_a, can_i):
        if can_a == 0 or can_i == 0:
            return 0
        else:
            return (can_a * can_i) % mod

    # 26 の累乗の配列
    pow_26 = [1] * (len(S) + 1)
    for i in range(1, len(S) + 1):
        pow_26[i] = (pow_26[i - 1] * 26) % mod

    # fact 配列（元のコードでは使われていませんが、用意してあります）
    fact = [1] * (len(S) + 1)
    for i in range(1, len(S) + 1):
        fact[i] = (fact[i - 1] * i) % mod

    ans = 0
    for i in range(N):
        if not (S[i] == 'o' or S[i] == '?'):
            continue
        cnt_a, cnt_i, cnt_h = 0, 0, 0
        cnt = 0
        if S[i] == '?':
            cnt += 1
        for j in G[i]:
            if S[j] == 'a':
                cnt_a += 1
            elif S[j] == 'i':
                cnt_i += 1
            elif S[j] == '?':
                cnt_h += 1
        ans = (ans + calc(cnt_a, cnt_i) * pow_26[total_q - cnt] + mod) % mod

        if total_q - cnt - 1 >= 0:
            ans = (ans + calc(cnt_a, cnt_h) * pow_26[total_q - cnt - 1] + mod) % mod
            ans = (ans + calc(cnt_h, cnt_i) * pow_26[total_q - cnt - 1] + mod) % mod

        if total_q - cnt - 2 >= 0:
            ans = (ans + cnt_h * (cnt_h - 1) * pow_26[total_q - cnt - 2] + mod) % mod

    print(ans)

if __name__ == '__main__':
    main()
0