結果
問題 | No.1340 おーじ君をさがせ |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2021-01-15 22:05:09 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,180 bytes |
コンパイル時間 | 439 ms |
コンパイル使用メモリ | 87,172 KB |
実行使用メモリ | 82,160 KB |
最終ジャッジ日時 | 2023-08-17 19:47:11 |
合計ジャッジ時間 | 14,798 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 77 ms
70,956 KB |
testcase_01 | AC | 76 ms
71,388 KB |
testcase_02 | AC | 75 ms
71,224 KB |
testcase_03 | AC | 77 ms
71,232 KB |
testcase_04 | WA | - |
testcase_05 | AC | 75 ms
71,396 KB |
testcase_06 | WA | - |
testcase_07 | AC | 74 ms
71,280 KB |
testcase_08 | AC | 75 ms
71,424 KB |
testcase_09 | AC | 77 ms
71,284 KB |
testcase_10 | AC | 87 ms
76,380 KB |
testcase_11 | AC | 174 ms
77,284 KB |
testcase_12 | WA | - |
testcase_13 | AC | 285 ms
78,180 KB |
testcase_14 | AC | 273 ms
77,124 KB |
testcase_15 | AC | 245 ms
77,152 KB |
testcase_16 | AC | 97 ms
76,388 KB |
testcase_17 | AC | 135 ms
77,220 KB |
testcase_18 | AC | 176 ms
77,412 KB |
testcase_19 | AC | 90 ms
76,612 KB |
testcase_20 | AC | 85 ms
76,316 KB |
testcase_21 | AC | 186 ms
77,324 KB |
testcase_22 | AC | 817 ms
82,160 KB |
testcase_23 | AC | 183 ms
77,488 KB |
testcase_24 | AC | 573 ms
78,064 KB |
testcase_25 | AC | 105 ms
77,184 KB |
testcase_26 | AC | 97 ms
76,692 KB |
testcase_27 | AC | 92 ms
76,728 KB |
testcase_28 | AC | 109 ms
77,312 KB |
testcase_29 | AC | 92 ms
76,608 KB |
testcase_30 | AC | 193 ms
77,496 KB |
testcase_31 | AC | 575 ms
78,184 KB |
testcase_32 | AC | 541 ms
78,040 KB |
testcase_33 | AC | 534 ms
77,908 KB |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | AC | 76 ms
71,168 KB |
testcase_37 | AC | 86 ms
76,104 KB |
testcase_38 | WA | - |
testcase_39 | AC | 214 ms
77,660 KB |
testcase_40 | AC | 218 ms
77,484 KB |
testcase_41 | AC | 220 ms
77,744 KB |
testcase_42 | WA | - |
testcase_43 | AC | 80 ms
76,232 KB |
testcase_44 | AC | 84 ms
75,960 KB |
testcase_45 | AC | 82 ms
76,292 KB |
testcase_46 | WA | - |
testcase_47 | WA | - |
testcase_48 | AC | 202 ms
77,460 KB |
testcase_49 | AC | 198 ms
77,236 KB |
testcase_50 | AC | 199 ms
77,532 KB |
testcase_51 | AC | 198 ms
77,424 KB |
testcase_52 | WA | - |
testcase_53 | WA | - |
testcase_54 | WA | - |
testcase_55 | WA | - |
testcase_56 | AC | 82 ms
76,300 KB |
testcase_57 | AC | 84 ms
76,484 KB |
testcase_58 | AC | 77 ms
71,224 KB |
testcase_59 | WA | - |
testcase_60 | AC | 75 ms
71,436 KB |
testcase_61 | WA | - |
ソースコード
""" NFAの状態数 行列べき乗じゃん!! """ import sys from sys import stdin mod = 998244353 #行列A,Bの積(不可能だとエラー,modに0以下の値を指定するとmodを取らなくなる) def matrix_mul(A,B): ans = [ [0] * len(B[0]) for i in range(len(A)) ] for ai in range(len(A)): for bj in range(len(B[0])): now = 0 for same in range(len(A[0])): now |= A[ai][same] & B[same][bj] ans[ai][bj] = now return ans #行列Aのx乗(当然正方行列じゃないとだめ) def matrix_pow(A,x): B = [[A[i][j] for j in range(len(A[0]))] for i in range(len(A))] ans = [[0] * len(A[0]) for i in range(len(A))] for i in range(len(A)): ans[i][i] = 1 while x > 0: if x % 2 == 1: ans = matrix_mul(ans,B) B = matrix_mul(B,B) x//=2 return ans N,M,T = map(int,stdin.readline().split()) H = [[0] * N for i in range(N)] for i in range(M): a,b = map(int,stdin.readline().split()) a -= 1 b -= 1 H[a][b] = 1 A = [[0] * N] A[0][0] = 1 ans = matrix_mul(A,matrix_pow(H,T)) #print (ans) print (sum(ans[0]))