結果

問題 No.3040 Aoiスコア
ユーザー N-noa21
提出日時 2025-02-28 22:24:56
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 111 ms / 1,000 ms
コード長 1,335 bytes
コンパイル時間 251 ms
コンパイル使用メモリ 82,912 KB
実行使用メモリ 77,940 KB
最終ジャッジ日時 2025-06-20 20:58:59
合計ジャッジ時間 3,185 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #

N,M = map(int, input().split())
S = list(input())
edge = [[] for i in range(N)]
mod = 998244353
for i in range(M):
    a,b = map(int, input().split())
    a-=1;b-=1
    edge[a].append(b)
    edge[b].append(a)
hatena_sum = S.count("?")
ans = 0
for i in range(N):
    if S[i] == "o" or S[i] == "?": 
        a_cnt = 0
        i_cnt = 0
        hatena_cnt = 0
        for _next in edge[i]:
            if S[_next] == "a":
                a_cnt += 1

            elif S[_next] == "i":
                i_cnt += 1
            elif S[_next] == "?":
                hatena_cnt += 1
        if S[i] == "o":
            ans += a_cnt * i_cnt * pow(26,hatena_sum,mod)#?そのまま
            ans += hatena_cnt * a_cnt * pow(26,hatena_sum-1,mod)#?を一つiに
            ans += hatena_cnt * i_cnt * pow(26,hatena_sum-1,mod)#?を一つaに
            ans += hatena_cnt * (hatena_cnt-1) * pow(26,hatena_sum-2,mod)#?と?
            ans %= mod
        else:#?を一つoとして使っている
            ans += a_cnt * i_cnt * pow(26,hatena_sum-1,mod)#?そのまま
            ans += hatena_cnt * a_cnt * pow(26,hatena_sum-2,mod)#?を一つiに
            ans += hatena_cnt * i_cnt * pow(26,hatena_sum-2,mod)#?を一つaに
            ans += hatena_cnt * (hatena_cnt-1) * pow(26,hatena_sum-3,mod)#?と?
            ans %= mod

print(ans%mod)
0