結果

問題 No.3175 転移迷宮 (Easy)
ユーザー LyricalMaestro
提出日時 2025-06-21 03:07:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,810 ms / 3,000 ms
コード長 2,560 bytes
コンパイル時間 507 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 82,784 KB
最終ジャッジ日時 2025-08-01 08:15:55
合計ジャッジ時間 48,518 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

MOD = 998244353

def calc_inv_matrix(N, matrix):
    inv_matrix = [[0] * N for _ in range(N)]
    for i in range(N):
        inv_matrix[i][i] = 1

    for i in range(N):
        if matrix[i][i] == 0:
            for k in range(i + 1, N):
                if matrix[k][i] != 0:
                    for j in range(N):
                        tmp = matrix[i][j]
                        matrix[i][j] = matrix[k][j]
                        matrix[k][j] = tmp

                        tmp = inv_matrix[i][j]
                        inv_matrix[i][j] = inv_matrix[k][j]
                        inv_matrix[k][j] = tmp
                    break

        # 1にする
        inv_alpha = pow(matrix[i][i], MOD - 2, MOD)
        for j in range(N):
            matrix[i][j] *= inv_alpha
            matrix[i][j] %= MOD
            inv_matrix[i][j] *= inv_alpha
            inv_matrix[i][j] %= MOD
        
        # 引く
        for k in range(i + 1, N):
            x = matrix[k][i]
            for j in range(N):
                matrix[k][j] -= (matrix[i][j] * x) % MOD
                matrix[k][j] %= MOD
                inv_matrix[k][j] -= (inv_matrix[i][j] * x) % MOD
                inv_matrix[k][j] %= MOD
    
    for i in reversed(range(N)):
        for k in range(i):
            x = matrix[k][i]
            for j in range(N):
                inv_matrix[k][j] -= (inv_matrix[i][j] * x) % MOD
                inv_matrix[k][j] %= MOD
    
    return inv_matrix


def solve(N, K):

    intercept = [1] * N

    matrix = [[0] * N for _ in range(N)]

    inv_k = pow(2 * K + 1, MOD - 2 , MOD)
    for i in range(N):
        cnt = 0
        for j in range(N):
            if  abs(i - j) <= K:
                cnt += 1
                matrix[i][j] = inv_k
        
    matrix2 = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if i == j:
                matrix2[i][j] = (1 - matrix[i][j]) % MOD
            else:
                matrix2[i][j] = (- matrix[i][j]) % MOD
    
    inv_matrix = calc_inv_matrix(N, matrix2)

    answer = [0] * N
    for i in range(N):
        for j in range(N):
            answer[i] += (inv_matrix[i][j] * intercept[j]) % MOD
            answer[i] %= MOD
    
    return " ".join(map(str, answer))




def main():
    T = int(input())
    answers = []
    for _ in range(T):
        N, K = map(int, input().split())
        ans = solve(N, K)
        answers.append(ans)

    for ans in answers:
        print(ans)




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