結果
問題 |
No.3175 転移迷宮 (Easy)
|
ユーザー |
|
提出日時 | 2025-06-06 22:38:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,642 ms / 3,000 ms |
コード長 | 7,692 bytes |
コンパイル時間 | 583 ms |
コンパイル使用メモリ | 82,320 KB |
実行使用メモリ | 82,032 KB |
最終ジャッジ日時 | 2025-06-06 22:39:42 |
合計ジャッジ時間 | 44,558 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 44 |
ソースコード
# 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 def GaussJordan_mod(a, mod, is_extended = False): """ in-plece 掃き出し 行列の慣習に合わせて、n, m が逆転しています """ n, m = len(a[0]), len(a) for i in range(m): for j in range(n): a[i][j] %= mod rank = 0 for col in range(n - is_extended): for row in range(rank, m): if a[row][col] != 0: pivot = row break else: continue a[pivot], a[rank] = a[rank], a[pivot] inv = pow(a[rank][col], mod-2, mod) for i in range(n): if a[rank][i] != 0: a[rank][i] = a[rank][i] * inv % mod for row in range(m): if row != rank and a[row][col] != 0: coef = a[row][col] for i in range(n): a[row][i] -= a[rank][i] * coef % mod if a[row][i] < 0: a[row][i] += mod rank += 1 return rank def GaussJordan_xor(n, a, is_extended = False): """ in-plece bit列での掃き出し n = 列数 """ m = len(a) rank = 0 for col in reversed(range(is_extended, n)): for row in range(rank, m): if a[row] >> col & 1: pivot = row break else: continue a[pivot], a[rank] = a[rank], a[pivot] for row in range(m): if row != rank and a[row] >> col & 1: a[row] ^= a[rank] rank += 1 return rank from copy import deepcopy def linear_equation(a, b, mod = None): """ 連立一次方程式を解く """ assert len(a) == len(b) if mod == 2: # m, n = len(a), len(a[0]) # mat = b.copy() # for i in range(m): # for j in range(n): # if a[i][j]: # mat[i] += 1 << j + 1 # rank = GaussJordan_xor(n+1, mat, True) # for row in range(rank, m): # if mat[row] & 1: return None, None # comp = [] # part = [] # row = 0 # for col in range(n): # if mat[row][col] == return comp, part else: m, n = len(a), len(a[0]) mat = deepcopy(a) for i in range(m): mat[i].append(b[i]) rank = GaussJordan_mod(mat, mod, True) # 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 comp, part def solve(): n, k = MI() a = [[0]*n 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 else: a[i][j] = 1 # print(a) # b = [0] * n b = [( - (2 * k + 1)) % mod] * n comp, part = linear_equation(a, b, mod) # if comp == None: # no() # exit() print(*part) # for i in range(n): ans = [0] t = II() for i in range(t): solve()