結果

問題 No.2832 Nana's Fickle Adventure
コンテスト
ユーザー LyricalMaestro
提出日時 2026-06-30 01:15:59
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 272 ms / 3,000 ms
コード長 3,108 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,006 ms
コンパイル使用メモリ 84,992 KB
実行使用メモリ 81,024 KB
最終ジャッジ日時 2026-06-30 01:16:22
合計ジャッジ時間 8,096 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/2832

MOD = 998244353

def prod_matrix(left, right):
    n = len(left)
    new_matrix = [[0 ] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                new_matrix[i][j] += (left[i][k] * right[k][j]) % MOD
                new_matrix[i][j] %= MOD
    return new_matrix

def prod_vector(matrix, vector):
    n = len(matrix)
    new_vector = [0] * n
    for i in range(n):
        for j in range(n):
            new_vector[i] += (matrix[i][j] * vector[j]) % MOD
            new_vector[i] %= MOD
    return new_vector

def to_edge_key(u, v):
    min_ = min(u, v)
    max_ = max(u, v)
    return min_, max_


def main():
    N, M, X = map(int, input().split())
    edges = {}
    for _ in range(M):
        u, v = map(int, input().split())
        key = to_edge_key(u - 1, v - 1)
        if key not in edges:
            edges[key] = 0
        edges[key] += 1
    
    key_array = []
    key_map = {}
    for i in range(N):
        for j in range(N):
            key_map[(i, j)] = len(key_array)
            key_array.append((i, j))
    
    # 1回目の移動
    tot_ans = 0
    for i in range(N):
        key = to_edge_key(i, 0)
        if key in edges:
            tot_ans += edges[key]
    
    prob_vector = [0] * (N ** 2)
    if tot_ans > 0:
        for i in range(N):
            key = to_edge_key(i, 0)
            if key in edges:
                p = edges[key]
                index = key_map[(i, 0)]
                prob_vector[index] = (p * pow(tot_ans, MOD - 2, MOD)) % MOD
    else:
        index = key_map[(0, 0)]
        prob_vector[index] = 1

    # 2回目以降の移動に備えたmatrix
    base_matrix = [[0] * (N ** 2) for _ in range(N ** 2)]
    for from_index in range(N ** 2):
        i, j = key_array[from_index]

        tot_ans = 0
        for k in range(N):
            key = to_edge_key(k, i)
            if key in edges:
                tot_ans += edges[key]
                if k == j:
                    tot_ans -= 1

        if tot_ans == 0:
            to_index = key_map[(i, i)]
            base_matrix[to_index][from_index] += 1
            base_matrix[to_index][from_index] %= MOD
        else:
            for k in range(N):
                key = to_edge_key(k, i)
                if key in edges:
                    x= edges[key]
                    if k == j:
                        x -= 1
                    to_index = key_map[(k, i)]
                    base_matrix[to_index][from_index] += (x * pow(tot_ans, MOD - 2, MOD)) % MOD
                    base_matrix[to_index][from_index] %= MOD

    M = X - 1
    while M > 0:
        if M % 2 == 1:
            prob_vector = prod_vector(base_matrix, prob_vector)
        
        base_matrix = prod_matrix(base_matrix, base_matrix)
        M //= 2
    answer = [0] * N
    for i in range(N):
        for j in range(N):
            index = key_map[(i, j)]
            answer[i] += prob_vector[index]
            answer[i] %= MOD
    for i in range(N):
        print(answer[i])
    



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