結果
問題 |
No.3176 転移迷宮 (Hard)
|
ユーザー |
|
提出日時 | 2025-06-06 22:58:52 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 7,434 bytes |
コンパイル時間 | 502 ms |
コンパイル使用メモリ | 82,636 KB |
実行使用メモリ | 345,796 KB |
最終ジャッジ日時 | 2025-06-06 22:58:58 |
合計ジャッジ時間 | 6,190 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | TLE * 1 -- * 40 |
ソースコード
# input import sys input = sys.stdin.readline II = lambda : int(input()) MI = lambda : map(int, input().split()) LI = lambda : [int(a) for a in input().split()] SI = lambda : input().rstrip() LLI = lambda n : [[int(a) for a in input().split()] for _ in range(n)] LSI = lambda n : [input().rstrip() for _ in range(n)] MI_1 = lambda : map(lambda x:int(x)-1, input().split()) LI_1 = lambda : [int(a)-1 for a in input().split()] def graph(n:int, m:int, dir:bool=False, index:int=-1) -> list[set[int]]: edge = [set() for i in range(n+1+index)] for _ in range(m): a,b = map(int, input().split()) a += index b += index edge[a].add(b) if not dir: edge[b].add(a) return edge def graph_w(n:int, m:int, dir:bool=False, index:int=-1) -> list[set[tuple]]: edge = [set() for i in range(n+1+index)] for _ in range(m): a,b,c = map(int, input().split()) a += index b += index edge[a].add((b,c)) if not dir: edge[b].add((a,c)) return edge mod = 998244353 inf = 1001001001001001001 ordalp = lambda s : ord(s)-65 if s.isupper() else ord(s)-97 ordallalp = lambda s : ord(s)-39 if s.isupper() else ord(s)-97 yes = lambda : print("Yes") no = lambda : print("No") yn = lambda flag : print("Yes" if flag else "No") def acc(a:list[int]): sa = [0]*(len(a)+1) for i in range(len(a)): sa[i+1] = a[i] + sa[i] return sa prinf = lambda ans : print(ans if ans < 1000001001001001001 else -1) alplow = "abcdefghijklmnopqrstuvwxyz" alpup = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" alpall = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" URDL = {'U':(-1,0), 'R':(0,1), 'D':(1,0), 'L':(0,-1)} DIR_4 = [[-1,0],[0,1],[1,0],[0,-1]] DIR_8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]] DIR_BISHOP = [[-1,1],[1,1],[1,-1],[-1,-1]] prime60 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59] sys.set_int_max_str_digits(0) sys.setrecursionlimit(10**6) # import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') from collections import defaultdict,deque from heapq import heappop,heappush from bisect import bisect_left,bisect_right DD = defaultdict BSL = bisect_left BSR = bisect_right # input import sys input = sys.stdin.readline II = lambda : int(input()) MI = lambda : map(int, input().split()) LI = lambda : [int(a) for a in input().split()] SI = lambda : input().rstrip() LLI = lambda n : [[int(a) for a in input().split()] for _ in range(n)] LSI = lambda n : [input().rstrip() for _ in range(n)] MI_1 = lambda : map(lambda x:int(x)-1, input().split()) LI_1 = lambda : [int(a)-1 for a in input().split()] def graph(n:int, m:int, dir:bool=False, index:int=-1) -> list[set[int]]: edge = [set() for i in range(n+1+index)] for _ in range(m): a,b = map(int, input().split()) a += index b += index edge[a].add(b) if not dir: edge[b].add(a) return edge def graph_w(n:int, m:int, dir:bool=False, index:int=-1) -> list[set[tuple]]: edge = [set() for i in range(n+1+index)] for _ in range(m): a,b,c = map(int, input().split()) a += index b += index edge[a].add((b,c)) if not dir: edge[b].add((a,c)) return edge mod = 998244353 inf = 1001001001001001001 ordalp = lambda s : ord(s)-65 if s.isupper() else ord(s)-97 ordallalp = lambda s : ord(s)-39 if s.isupper() else ord(s)-97 yes = lambda : print("Yes") no = lambda : print("No") yn = lambda flag : print("Yes" if flag else "No") def acc(a:list[int]): sa = [0]*(len(a)+1) for i in range(len(a)): sa[i+1] = a[i] + sa[i] return sa prinf = lambda ans : print(ans if ans < 1000001001001001001 else -1) alplow = "abcdefghijklmnopqrstuvwxyz" alpup = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" alpall = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" URDL = {'U':(-1,0), 'R':(0,1), 'D':(1,0), 'L':(0,-1)} DIR_4 = [[-1,0],[0,1],[1,0],[0,-1]] DIR_8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]] DIR_BISHOP = [[-1,1],[1,1],[1,-1],[-1,-1]] prime60 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59] sys.set_int_max_str_digits(0) sys.setrecursionlimit(10**6) # import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') from collections import defaultdict,deque from heapq import heappop,heappush from bisect import bisect_left,bisect_right DD = defaultdict BSL = bisect_left BSR = bisect_right MOD = 998244353 def modinv(x): return pow(x, MOD - 2, MOD) def sparse_gauss_jordan_mod(matrix, num_cols): """ 掃き出し法(mod付き、列→行マップで最適化) matrix: list of dicts (i行目は {列番号: 値}) 例: [{1:3, 4:5}, {2:1}] num_cols: 列数(未知数の個数) """ n = len(matrix) rank = 0 # 各列に非ゼロを持つ行を記録 rows_with = defaultdict(set) for i, row in enumerate(matrix): for j in row: rows_with[j].add(i) for col in range(num_cols): pivot = -1 for row in rows_with[col]: if row >= rank and matrix[row].get(col, 0) != 0: pivot = row break if pivot == -1: continue # ピボットをrank番目に移動 if pivot != rank: matrix[rank], matrix[pivot] = matrix[pivot], matrix[rank] # rows_withの更新 for j in matrix[rank]: rows_with[j].discard(pivot) rows_with[j].add(rank) for j in matrix[pivot]: rows_with[j].discard(rank) rows_with[j].add(pivot) # ピボットを1に正規化 inv = modinv(matrix[rank][col]) for j in list(matrix[rank].keys()): matrix[rank][j] = matrix[rank][j] * inv % MOD # 他の行の消去 for row in list(rows_with[col]): if row != rank and col in matrix[row]: factor = matrix[row][col] for j in matrix[rank]: val = (factor * matrix[rank][j]) % MOD matrix[row][j] = (matrix[row].get(j, 0) - val) % MOD if matrix[row][j] == 0: del matrix[row][j] rows_with[j].discard(row) else: rows_with[j].add(row) if col in matrix[row]: del matrix[row][col] rows_with[col].discard(row) rank += 1 return rank from copy import deepcopy def linear_equation(n, m, a, b, mod = None): """ 連立一次方程式を解く """ assert len(a) == len(b) mat = deepcopy(a) for i in range(m): mat[i][n] = b[i] # print(mat) rank = sparse_gauss_jordan_mod(mat, n) # print(mat, rank) for row in range(rank, m): if mat[row][n]: return None, None part = [mat[i][n] for i in range(rank)] # comp = mat[:rank] # for i in range(rank): # comp[i].pop() return part def solve(): n, k = MI() a = [dict() for i in range(n)] for i in range(n): for j in range(i - k, i + k + 1): if j < 0 or n <= j: continue if i == j: a[i][j] = (- 2 * k) % mod else: a[i][j] = 1 b = [(-(2 * k + 1)) % mod] * n part = linear_equation(n, n, a, b, mod) print(*part) t = II() for i in range(t): solve()