結果
問題 | No.1340 おーじ君をさがせ |
ユーザー | None |
提出日時 | 2021-04-04 16:37:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,023 ms / 2,000 ms |
コード長 | 11,087 bytes |
コンパイル時間 | 316 ms |
コンパイル使用メモリ | 87,104 KB |
実行使用メモリ | 82,124 KB |
最終ジャッジ日時 | 2023-08-27 17:31:17 |
合計ジャッジ時間 | 15,222 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 77 ms
71,040 KB |
testcase_01 | AC | 74 ms
70,936 KB |
testcase_02 | AC | 73 ms
70,992 KB |
testcase_03 | AC | 72 ms
70,944 KB |
testcase_04 | AC | 77 ms
70,588 KB |
testcase_05 | AC | 71 ms
70,768 KB |
testcase_06 | AC | 73 ms
70,696 KB |
testcase_07 | AC | 72 ms
71,080 KB |
testcase_08 | AC | 72 ms
70,780 KB |
testcase_09 | AC | 71 ms
70,928 KB |
testcase_10 | AC | 96 ms
76,324 KB |
testcase_11 | AC | 174 ms
77,200 KB |
testcase_12 | AC | 98 ms
76,200 KB |
testcase_13 | AC | 329 ms
77,812 KB |
testcase_14 | AC | 260 ms
77,172 KB |
testcase_15 | AC | 255 ms
77,112 KB |
testcase_16 | AC | 94 ms
76,496 KB |
testcase_17 | AC | 135 ms
76,804 KB |
testcase_18 | AC | 182 ms
77,228 KB |
testcase_19 | AC | 87 ms
75,840 KB |
testcase_20 | AC | 81 ms
75,904 KB |
testcase_21 | AC | 180 ms
77,344 KB |
testcase_22 | AC | 1,023 ms
82,124 KB |
testcase_23 | AC | 178 ms
76,988 KB |
testcase_24 | AC | 550 ms
78,248 KB |
testcase_25 | AC | 100 ms
77,084 KB |
testcase_26 | AC | 96 ms
77,096 KB |
testcase_27 | AC | 93 ms
76,468 KB |
testcase_28 | AC | 105 ms
77,392 KB |
testcase_29 | AC | 87 ms
76,652 KB |
testcase_30 | AC | 187 ms
77,404 KB |
testcase_31 | AC | 632 ms
78,176 KB |
testcase_32 | AC | 504 ms
78,024 KB |
testcase_33 | AC | 505 ms
77,896 KB |
testcase_34 | AC | 457 ms
77,428 KB |
testcase_35 | AC | 537 ms
78,132 KB |
testcase_36 | AC | 74 ms
70,908 KB |
testcase_37 | AC | 81 ms
75,884 KB |
testcase_38 | AC | 633 ms
78,356 KB |
testcase_39 | AC | 198 ms
77,040 KB |
testcase_40 | AC | 206 ms
77,400 KB |
testcase_41 | AC | 204 ms
77,340 KB |
testcase_42 | AC | 81 ms
76,196 KB |
testcase_43 | AC | 80 ms
76,196 KB |
testcase_44 | AC | 86 ms
76,064 KB |
testcase_45 | AC | 82 ms
76,040 KB |
testcase_46 | AC | 188 ms
77,284 KB |
testcase_47 | AC | 197 ms
77,156 KB |
testcase_48 | AC | 203 ms
77,528 KB |
testcase_49 | AC | 212 ms
77,520 KB |
testcase_50 | AC | 200 ms
77,256 KB |
testcase_51 | AC | 203 ms
77,156 KB |
testcase_52 | AC | 279 ms
77,496 KB |
testcase_53 | AC | 283 ms
77,488 KB |
testcase_54 | AC | 280 ms
77,392 KB |
testcase_55 | AC | 256 ms
77,612 KB |
testcase_56 | AC | 80 ms
75,720 KB |
testcase_57 | AC | 80 ms
76,296 KB |
testcase_58 | AC | 71 ms
71,096 KB |
testcase_59 | AC | 146 ms
77,544 KB |
testcase_60 | AC | 74 ms
70,844 KB |
testcase_61 | AC | 152 ms
76,980 KB |
ソースコード
######################################################### """ ## 和&積(MOD無し) ####################################### def mul2(a,b): return a*b def add2(a,b): return a+b def mul_inv2(a): return 1/a def add_inv2(a): return -a def identity(n): return Matrix([[int(i==j) for i in range(n)] for j in range(n)]) ########################################################### ## 和&積(MOD有り) ####################################### MOD=10**9+7 def mul2(a,b): return a*b%MOD def add2(a,b): return (a+b)%MOD def mul_inv2(a): return pow(a,MOD-2,MOD) def add_inv2(a): return -a%MOD def identity(n): return Matrix([[int(i==j) for i in range(n)] for j in range(n)]) ########################################################### ## 論理和&論理積 ####################################### def mul2(a,b): return a&b def add2(a,b): return a^b def mul_inv2(a): return None def add_inv2(a): return a mask=(1<<101)-1 def identity(n): return Matrix([[int(i==j)*mask for i in range(n)] for j in range(n)]) ########################################################### """ ######################################################### class Matrix(): def __init__(self,A): self.H=len(A) self.W=len(A[0]) self._matrix=A # for i in range(self.row): # for j in range(self.column): def __getitem__(self,item): if type(item)==tuple: i,j=item return self._matrix[i][j] else: return self._matrix[item] def __setitem__(self,item,val): i,j=item self._matrix[i][j]=val def __add__(self,B): # assert (self.row,self.column)==(other.row,other.column), "sizes of matrices are different" H,W,A=self.H,self.W,self._matrix AB=[[0]*W for _ in range(H)] for h in range(H): for w in range(W): AB[h][w]=add2(A[h][w],B._matrix[h][w]) return Matrix(AB) def __mul__(self,other): H,W,A=self.H,self.W,self._matrix if type(other)==int: n=other AB=[[(mul2(n,A[i][j])) for j in range(W)] for i in range(H)] return Matrix(AB) elif type(other)==Vector: vec=other res=[0]*W for i in range(H): for j in range(W): res[i]=add2(res[i],mul2(A[i][j],vec[j])) return Vector(res) else: # assert self.column!=other.row, "sizes of matrices are different" AB=[[0]*other.W for _ in range(H)] for i in range(H): for j in range(other.W): temp=0 for k in range(W): temp=add2(temp,mul2(A[i][k],other._matrix[k][j])) AB[i][j]=temp return Matrix(AB) def __truediv__(self,c): H,W,A=self.H,self.W,self._matrix res=A.copy() for h in range(H): for w in range(W): res[h][w]=mul2(res[h][w],mul_inv2(c)) return Matrix(res) def __floordiv__(self,c): H,W,A=self.H,self.W,self._matrix res=A.copy() for h in range(H): for w in range(W): res[h][w]=res[h][w]//c return Matrix(res) def __mod__(self,c): H,W,A=self.H,self.W,self._matrix res=A.copy() for h in range(H): for w in range(W): res[h][w]=res[h][w]%c return Matrix(res) def __pow__(self,m): # assert self.column==self.row, "the size of row must be the same as that of column" H,W,A=self.H,self.W,self._matrix if m==0: return identity(H) else: m-=1 res=self while m: if m%2==1: res=res*self self=self*self m>>=1 return res def __eq__(self,other): if type(other)==Matrix: return self._matrix==other._matrix return False def __ne__(self,other): if type(other)==Matrix: return self._matrix!=other._matrix return True def __len__(self): return self.H def __str__(self): res=[] for i in range(self.H): for j in range(self.W): res.append(str(self._matrix[i][j])) res.append(" ") res.append("\n") return "".join(res) def __hash__(self): res=[] for h in range(self.H): for w in range(self.W): res.append(self._matrix[h][w]) return tuple(res) def det(self): H,W,A=self.H,self.W,self._matrix n=H res=1 for i in range(n): if A[i][i]==0: res=add_inv2(res) for k in range(i+1,n): if A[k][i]!=0: A[i],A[k]=A[k],A[i] break else: return 0 c=mul_inv2(A[i][i]) for j in range(i+1,n): l=mul2(c,A[j][i]) for k in range(i+1,n): A[j][k]=add2(A[j][k],add_inv2(l*A[i][k])) for i in range(n): res=mul2(res,A[i][i]) return res def map(self,func): # act func to all elements H,W,A=self.H,self.W,self._matrix res=A.copy() for h in range(H): for w in range(W): res[h][w]=func(res[h][w]) return Matrix(res) def count(self,x): cnt=0 for h in range(self.H): for w in range(self.W): cnt+=(self._matrix[h][w]==x) return cnt def rank(self): """ = dimension""" H,W,A=self.H,self.W,self._matrix A=[self._matrix[i][:] for i in range(H)] rank=0 p,q=[],[] for w in range(W): for h in range(rank,H): if A[h][w]!=0: break else: q.append(w) continue if w==W: return -1,[],[] p.append(w) A[rank],A[h]=A[h],A[rank] inv=mul_inv2(A[rank][w]) for ww in range(W): A[rank][ww]=mul2(A[rank][ww],inv) for h in range(H): if h==rank: continue c=add_inv2(A[h][w]) for ww in range(W): A[h][ww]=add2(A[h][ww],mul2(c,A[rank][ww])) rank+=1 return rank class Vector(): def __init__(self,vec): self.n=len(vec) self._vector=vec def __getitem__(self,item): return self._vector[item] def __setitem__(self,item,val): self._vector[item]=val def __neg__(self): n,vec=self.n,self._vector res=[] for x in vec: res.append(add_inv2(x)) return Vector(res) def __add__(self,vec2): n,vec=self.n,self._vector res=vec.copy() for i in range(n): res[i]=add2(res[i],vec2[i]) return Vector(res) def __sub__(self,vec2): n,vec=self.n,self._vector res=vec.copy() for i in range(n): res[i]=add2(res[i],add_inv2(vec2[i])) return Vector(res) def __mul__(self,vec2): n,vec=self.n,self._vector if type(vec2)!=int: res=vec.copy() for i in range(n): res[i]=mul2(res[i],vec2[i]) return Vector(res) else: res=[mul2(vec2,vec[i]) for i in range(n)] return Vector(res) def __truediv__(self,c): n,vec=self.n,self._vector res=vec.copy() for i in range(n): res[i]=mul2(res[i],mul_inv2(c)) return Vector(res) def __floordiv__(self,c): n,vec=self.n,self._vector res=vec.copy() for i in range(n): res[i]=res[i]//c return Vector(res) def __mod__(self,c): n,vec=self.n,self._vector res=vec.copy() for i in range(n): res[i]=res[i]%c return Vector(res) def map(self,func): # act func to all elements n,vec=self.n,self._vector res=vec.copy() for i in range(n): res[i]=func(res[i]) return Vector(res) def __eq__(self,other): if type(other)==Vector: return self._vector==other._vector return False def __ne__(self,other): if type(other)==Vector: return self._vector!=other._vector return True def __len__(self): return self.n def __str__(self): res=[] for i in range(self.n): res.append(str(self._vector[i])) res.append(" ") return "".join(res) def __hash__(self): return tuple(self._vector) def count(self,x): cnt=0 for a in self._vector: cnt+=(a==x) return cnt def linear_equations(mat, vec): """ return (dim, [x,y,z], [[a0,b0,c0],[a1,b1,c1],...]) which means, solution = (x,y,z)+t0*(a0,b0,c0)+t1*(a1,b1,c1)+... Cation: float """ H, W = len(mat), len(mat[0]) # assert H == len(vec) aug = [mat[i] + [vec[i]] for i in range(H)] rank = 0 p,q = [],[] for w in range(W + 1): for h in range(rank, H): if aug[h][w] != 0: break else: q.append(w) continue if w == W: return -1, [], [] p.append(w) aug[rank], aug[h] = aug[h], aug[rank] inv = mul_inv2(aug[rank][w]) for ww in range(W + 1): aug[rank][ww] = mul2(aug[rank][ww], inv) for h in range(H): if h == rank: continue c = add_inv2(aug[h][w]) for ww in range(W + 1): aug[h][ww] = add2(aug[h][ww], mul2(c,aug[rank][ww])) rank += 1 dim = W - rank sol = [0] * W for h in range(rank): sol[p[h]] = aug[h][-1] vecs = [[0] * W for _ in range(dim)] for h in range(dim): vecs[h][q[h]] = 1 for h in range(dim): for w in range(rank): vecs[h][p[w]] = add_inv2(aug[w][q[h]]) return dim, sol, vecs ########################################################### def example(): global input example = iter( """ 2 3 1 2 3 4 5 6 50 122 """ .strip().split("\n")) input = lambda: next(example) ## 論理和&論理積 ####################################### def mul2(a,b): return a&b def add2(a,b): return a|b def mul_inv2(a): return None def add_inv2(a): return a mask=(1<<101)-1 def identity(n): return Matrix([[int(i==j)*mask for i in range(n)] for j in range(n)]) ########################################################### import sys input = sys.stdin.readline N,M,T=map(int, input().split()) mat=[[0]*N for _ in range(N)] for _ in range(M): a,b=map(int, input().split()) mat[b][a]=1 mat=Matrix(mat) vec=Vector([1]+[0]*(N-1)) print(sum((mat**T)*vec))