結果

問題 No.762 PDCAパス
ユーザー tails1434
提出日時 2020-01-15 07:25:33
言語 PyPy3
(7.0.0)
結果
AC  
実行時間 328 ms
コード長 1,279 Byte
コンパイル時間 1,768 ms
使用メモリ 93,164 KB
最終ジャッジ日時 2020-01-15 07:25:45

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0sample1.txt AC 108 ms
78,072 KB
0sample2.txt AC 104 ms
78,256 KB
0sample3.txt AC 104 ms
78,296 KB
1ddcc.txt AC 104 ms
78,276 KB
1ppap.txt AC 108 ms
78,056 KB
1tiny0.txt AC 108 ms
78,052 KB
1tiny1.txt AC 104 ms
78,576 KB
1tiny2.txt AC 108 ms
78,236 KB
2simple0.txt AC 104 ms
78,052 KB
2simple1.txt AC 108 ms
78,056 KB
2simple2.txt AC 104 ms
78,572 KB
2simple3.txt AC 104 ms
78,580 KB
2simple4.txt AC 108 ms
78,192 KB
2simple5.txt AC 104 ms
78,168 KB
2simple6.txt AC 108 ms
78,164 KB
3complex0.txt AC 108 ms
78,360 KB
3complex1.txt AC 108 ms
78,244 KB
4random1.txt AC 108 ms
78,232 KB
4random2.txt AC 104 ms
78,072 KB
4random3.txt AC 108 ms
78,244 KB
4random4.txt AC 104 ms
78,436 KB
4random5.txt AC 104 ms
78,308 KB
5test1_1.txt AC 220 ms
80,724 KB
5test1_2.txt AC 220 ms
80,596 KB
5test2_1.txt AC 288 ms
93,000 KB
5test2_2.txt AC 272 ms
93,164 KB
5test3_1.txt AC 200 ms
80,884 KB
5test3_2.txt AC 204 ms
81,076 KB
6random11.txt AC 328 ms
90,636 KB
6random12.txt AC 320 ms
90,240 KB
6random21.txt AC 324 ms
88,356 KB
6random22.txt AC 308 ms
88,016 KB
6random23.txt AC 312 ms
88,496 KB
6random31.txt AC 308 ms
86,116 KB
6random32.txt AC 312 ms
86,648 KB
6random33.txt AC 292 ms
85,856 KB
6random41.txt AC 268 ms
82,816 KB
6random42.txt AC 272 ms
82,432 KB
6random43.txt AC 280 ms
83,108 KB
6random44.txt AC 272 ms
83,080 KB
6random45.txt AC 284 ms
83,108 KB
テストケース一括ダウンロード

ソースコード

diff #
import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    S = input()
    d = [[] for _ in range(N)]
    MOD = 10 ** 9 + 7
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        if S[u] == 'P' and S[v] == 'D':
            d[u].append(v)
        if S[u] == 'D' and S[v] == 'C':
            d[u].append(v)
        if S[u] == 'C' and S[v] == 'A':
            d[u].append(v)
        if S[v] == 'P' and S[u] == 'D':
            d[v].append(u)
        if S[v] == 'D' and S[u] == 'C':
            d[v].append(u)
        if S[v] == 'C' and S[u] == 'A':
            d[v].append(u)
    
    dp = [[0] * N for _ in range(4)]

    for i in range(N):
        if S[i] == 'P':
            dp[0][i] = 1
    
    for u in range(N):
        for v in d[u]:
            if S[v] == 'D':
                dp[1][v] += dp[0][u]
                dp[1][v] %= MOD
    
    for u in range(N):
        for v in d[u]:
            if S[v] == 'C':
                dp[2][v] += dp[1][u]
                dp[2][v] %= MOD
    
    for u in range(N):
        for v in d[u]:
            if S[v] == 'A':
                dp[3][v] += dp[2][u]
                dp[3][v] %= MOD

    print(sum(dp[3]) % MOD)

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