結果

問題 No.1340 おーじ君をさがせ
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:50:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 167 ms / 2,000 ms
コード長 1,764 bytes
コンパイル時間 482 ms
コンパイル使用メモリ 82,092 KB
実行使用メモリ 78,076 KB
最終ジャッジ日時 2025-04-15 21:52:42
合計ジャッジ時間 6,350 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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)]
    out_degree = [0] * n
    for _ in range(m):
        a = int(input[idx]); idx +=1
        b = int(input[idx]); idx +=1
        edges[a].append(b)
        out_degree[a] += 1

    # Construct the adjacency matrix with bitmask
    mask = [0] * n
    for u in range(n):
        if out_degree[u] == 0:
            mask[u] = 0
        else:
            for v in edges[u]:
                mask[u] |= 1 << v

    if t == 0:
        print(1)
        return

    def multiply(A, B):
        n = len(A)
        # Compute transpose of B as bitmask for each column
        BT = [0] * n
        for j in range(n):
            bt = 0
            for k in range(n):
                if (B[k] >> j) & 1:
                    bt |= 1 << k
            BT[j] = bt
        # Compute product matrix C
        C = [0] * n
        for i in range(n):
            ci = 0
            for j in range(n):
                if (A[i] & BT[j]) != 0:
                    ci |= 1 << j
            C[i] = ci
        return C

    def matrix_power(mat, power):
        n = len(mat)
        # Initialize result as identity matrix
        result = [0] * n
        for i in range(n):
            result[i] = 1 << i  # Each row has only the i-th bit set
        while power > 0:
            if power % 2 == 1:
                result = multiply(result, mat)
            mat = multiply(mat, mat)
            power = power // 2
        return result

    mat_pow = matrix_power(mask, t)
    row0 = mat_pow[0]
    count = bin(row0).count('1')
    print(count)

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