結果

問題 No.1340 おーじ君をさがせ
ユーザー lam6er
提出日時 2025-04-15 23:26:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 106 ms / 2,000 ms
コード長 1,664 bytes
コンパイル時間 262 ms
コンパイル使用メモリ 81,476 KB
実行使用メモリ 76,848 KB
最終ジャッジ日時 2025-04-15 23:28:29
合計ジャッジ時間 4,727 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    T = int(input[idx]); idx +=1
    
    edges = [[] for _ in range(N)]
    for _ in range(M):
        a = int(input[idx]); idx +=1
        b = int(input[idx]); idx +=1
        edges[a].append(b)
    
    dead_end = [len(e) == 0 for e in edges]
    
    if T == 0:
        print(1)
        return
    
    if dead_end[0]:
        print(0)
        return
    
    # Build modified adjacency matrix as bitmask rows
    modified_adj = [0] * N
    for a in range(N):
        if not dead_end[a]:
            mask = 0
            for b in edges[a]:
                mask |= 1 << b
            modified_adj[a] = mask
    
    def multiply(a, b):
        res = [0] * N
        for i in range(N):
            row = a[i]
            temp = 0
            k = 0
            while row:
                if row & 1:
                    temp |= b[k]
                row >>= 1
                k += 1
            res[i] = temp
        return res
    
    def matrix_power(mat, power):
        # Initialize result as identity matrix
        result = [0] * N
        for i in range(N):
            result[i] = 1 << i  # Identity matrix: each node can reach itself in 0 steps
        current = mat.copy()
        while power > 0:
            if power % 2 == 1:
                result = multiply(result, current)
            current = multiply(current, current)
            power = power // 2
        return result
    
    mat_power = matrix_power(modified_adj, T)
    print(bin(mat_power[0]).count('1'))

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