結果

問題 No.1112 冥界の音楽
ユーザー lam6er
提出日時 2025-03-20 21:06:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 108 ms / 2,000 ms
コード長 2,014 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 76,508 KB
最終ジャッジ日時 2025-03-20 21:06:31
合計ジャッジ時間 3,221 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

K, M, N = map(int, input().split())

allowed = set()
for _ in range(M):
    p, q, r = map(int, input().split())
    allowed.add((p, q, r))

# Generate all possible states (a, b)
states = []
index = {}
for a in range(1, K + 1):
    for b in range(1, K + 1):
        states.append((a, b))
        index[(a, b)] = len(states) - 1

size = len(states)

# Initialize transition matrix
matrix = [[0] * size for _ in range(size)]
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            if (a, b, c) in allowed:
                if (a, b) in index and (b, c) in index:
                    i = index[(a, b)]
                    j = index[(b, c)]
                    matrix[i][j] += 1

# Matrix exponentiation functions
def multiply(a, b):
    res = [[0] * size for _ in range(size)]
    for i in range(size):
        for k in range(size):
            if a[i][k] == 0:
                continue
            for j in range(size):
                res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % MOD
    return res

def matrix_power(mat, power):
    result = [[0] * size for _ in range(size)]
    for i in range(size):
        result[i][i] = 1
    while power > 0:
        if power % 2 == 1:
            result = multiply(result, mat)
        mat = multiply(mat, mat)
        power //= 2
    return result

if N == 1 or N == 2:
    print(1 if N == 1 and K >= 1 else 0)
    exit()

pow_count = N - 2
mat = matrix_power(matrix, pow_count)

# Initial vector: starts with (1, b) for all b
initial = [0] * size
for b in range(1, K + 1):
    key = (1, b)
    if key in index:
        initial[index[key]] = 1

# Multiply initial vector with the exponentiated matrix
result = [0] * size
for i in range(size):
    if initial[i]:
        for j in range(size):
            result[j] = (result[j] + initial[i] * mat[i][j]) % MOD

# Sum all states ending with 1
answer = 0
for (a, b), idx in index.items():
    if b == 1:
        answer = (answer + result[idx]) % MOD

print(answer)
0