結果
問題 | No.1421 国勢調査 (Hard) |
ユーザー | vwxyz |
提出日時 | 2023-05-24 20:02:10 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 26,527 bytes |
コンパイル時間 | 220 ms |
コンパイル使用メモリ | 16,128 KB |
実行使用メモリ | 37,504 KB |
最終ジャッジ日時 | 2024-12-23 20:22:36 |
合計ジャッジ時間 | 36,502 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 11 TLE * 10 WA * 9 |
ソースコード
import sysreadline=sys.stdin.readlineclass Matrix:def __init__(self,H=0,W=0,matrix=False,eps=0,mod=0,identity=0):if identity:if H:self.H=Hself.W=Helse:self.H=Wself.W=Wself.matrix=[[0]*self.W for i in range(self.H)]for i in range(self.H):self.matrix[i][i]=identityelif matrix:self.matrix=matrixself.H=len(self.matrix)self.W=len(self.matrix[0]) if self.matrix else 0else:self.H=Hself.W=Wself.matrix=[[0]*self.W for i in range(self.H)]self.mod=modself.eps=epsdef __eq__(self,other):if type(other)!=Matrix:return Falseif self.H!=other.H:return Falseif self.mod:for i in range(self.H):for j in range(self.W):if self.matrix[i][j]%self.mod!=other.matrix[i][j]%self.mod:return Falseelse:for i in range(self.H):for j in range(self.W):if self.eps<abs(self.matrix[i][j]-other.matrix[i][j]):return Falsereturn Truedef __ne__(self,other):if type(other)!=Matrix:return Trueif self.H!=other.H:return Trueif self.mod:for i in range(self.H):for j in range(self.W):if self.matrix[i][j]%self.mod!=other.matrix[i][j]%self.mod:return Trueelse:for i in range(self.H):for j in range(self.W):if self.eps<abs(self.matrix[i][j]-other.matrix[i][j]):return Truereturn Falsedef __add__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wif self.mod:summ=Matrix(matrix=[[(self.matrix[i][j]+other.matrix[i][j])%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:summ=Matrix(matrix=[[self.matrix[i][j]+other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:if self.mod:summ=Matrix(matrix=[[(self.matrix[i][j]+other)%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:summ=Matrix(matrix=[[self.matrix[i][j]+other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)return summdef __sub__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wif self.mod:diff=Matrix(matrix=[[(self.matrix[i][j]-other.matrix[i][j])%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:diff=Matrix(matrix=[[self.matrix[i][j]-other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:if self.mod:diff=Matrix(matrix=[[(self.matrix[i][j]-other)%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:diff=Matrix(matrix=[[self.matrix[i][j]-other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)return diffdef __mul__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wif self.mod:prod=Matrix(matrix=[[(self.matrix[i][j]*other.matrix[i][j])%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:prod=Matrix(matrix=[[self.matrix[i][j]*other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:if self.mod:prod=Matrix(matrix=[[(self.matrix[i][j]*other)%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:prod=Matrix(matrix=[[self.matrix[i][j]*other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)return proddef __matmul__(self,other):if type(other)==Matrix:assert self.W==other.Hprod=Matrix(H=self.H,W=other.W,eps=self.eps,mod=self.mod)for i in range(self.H):for j in range(other.W):for k in range(self.W):prod.matrix[i][j]+=self.matrix[i][k]*other.matrix[k][j]if self.mod:prod.matrix[i][j]%=self.modelif type(other)==int:assert self.H==self.Wif other==0:prod=Matrix(H=self.H,eps=self.eps,mod=self.mod,identity=1)elif other==1:prod=Matrix(matrix=[[self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:prod=Matrix(H=self.H,eps=self.eps,mod=self.mod,identity=1)doub=Matrix(matrix=[[self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)while other>=2:if other&1:prod@=doubdoub@=doubother>>=1prod@=doubreturn proddef __truediv__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wif self.mod:quot=Matrix(matrix=[[(self.matrix[i][j]*MOD(self.mod).Pow(other.matrix[i][j],-1))%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:quot=Matrix(matrix=[[self.matrix[i][j]/other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:if self.mod:inve=MOD(self.mod).Pow(other,-1)quot=Matrix(matrix=[[(self.matrix[i][j]*inve)%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:quot=Matrix(matrix=[[self.matrix[i][j]/other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)return quotdef __floordiv__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wquot=Matrix(matrix=[[self.matrix[i][j]//other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:quot=Matrix(matrix=[[self.matrix[i][j]//other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)return quotdef __mod__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wrema=Matrix(matrix=[[self.matrix[i][j]%other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:rema=Matrix(matrix=[[self.matrix[i][j]%other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)return remadef __pow__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wif self.mod:powe=Matrix(matrix=[[pow(self.matrix[i][j],other.matrix[i][j],self.mod) for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:powe=Matrix(matrix=[[pow(self.matrix[i][j],other.matrix[i][j]) for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:if self.mod:powe=Matrix(matrix=[[pow(self.matrix[i][j],other,self.mod) for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:powe=Matrix(matrix=[[pow(self.matrix[i][j],other) for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)return powedef __lshift__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wlshi=Matrix(matrix=[[self.matrix[i][j]<<other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:lshi=Matrix(matrix=[[self.matrix[i][j]<<other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)return lshidef __rshift__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wrshi=Matrix(matrix=[[self.matrix[i][j]>>other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:rshi=Matrix(matrix=[[self.matrix[i][j]>>other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)return rshidef __and__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wconj=Matrix(matrix=[[self.matrix[i][j]&other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:conj=Matrix(matrix=[[self.matrix[i][j]&other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)return conjdef __or__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wdisj=Matrix(matrix=[[self.matrix[i][j]|other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:disj=Matrix(matrix=[[self.matrix[i][j]|other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)return disjdef __xor__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wexcl=Matrix(matrix=[[self.matrix[i][j]^other.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:excl=Matrix(matrix=[[self.matrix[i][j]^other for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)return excldef __iadd__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor i in range(self.H):for j in range(self.W):self.matrix[i][j]+=other.matrix[i][j]if self.mod:self.matrix[i][j]%=self.modelse:for i in range(self.H):for j in range(self.W):self.matrix[i][j]+=otherif self.mod:self.matrix[i][j]%=self.modreturn selfdef __isub__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor i in range(self.H):for j in range(self.W):self.matrix[i][j]-=other.matrix[i][j]if self.mod:self.matrix[i][j]%=self.modelse:for i in range(self.H):for j in range(self.W):self.matrix[i][j]-=otherif self.mod:self.matrix[i][j]%=self.modreturn selfdef __imul__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor i in range(self.H):for j in range(self.W):self.matrix[i][j]*=other.matrix[i][j]if self.mod:self.matrix[i][j]%=self.modelse:for i in range(self.H):for j in range(self.W):self.matrix[i][j]*=otherif self.mod:self.matrix[i][j]%=self.modreturn selfdef __imatmul__(self,other):if type(other)==Matrix:assert self.W==other.Hprod=Matrix(H=self.H,W=other.W,eps=self.eps,mod=self.mod)for i in range(self.H):for j in range(other.W):for k in range(self.W):prod.matrix[i][j]+=self.matrix[i][k]*other.matrix[k][j]if self.mod:prod.matrix[i][j]%=self.modelif type(other)==int:assert self.H==self.Wif other==0:return Matrix(H=self.H,eps=self.eps,mod=self.mod,identity=1)elif other==1:prod=Matrix(matrix=[[self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:prod=Matrix(H=self.H,eps=self.eps,mod=self.mod,identity=1)doub=selfwhile other>=2:if other&1:prod@=doubdoub@=doubother>>=1prod@=doubreturn proddef __itruediv__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor i in range(self.H):for j in range(self.W):if self.mod:self.matrix[i][j]=self.matrix[i][j]*MOD(self.mod).Pow(other.matrix[i][j],-1)%self.modelse:self.matrix[i][j]/=other.matrix[i][j]else:if self.mod:inve=MOD(self.mod).Pow(other,-1)for i in range(self.H):for j in range(self.W):if self.mod:self.matrix[i][j]=self.matrix[i][j]*inve%self.modelse:self.matrix[i][j]/=otherreturn selfdef __ifloordiv__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor i in range(self.H):for j in range(self.W):self.matrix[i][j]//=other.matrix[i][j]else:for i in range(self.H):for j in range(self.W):self.matrix[i][j]//=otherreturn selfdef __imod__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor i in range(self.H):for j in range(self.W):self.matrix[i][j]%=other.matrix[i][j]else:for i in range(self.H):for j in range(self.W):self.matrix[i][j]%=otherreturn selfdef __ipow__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor i in range(self.H):for j in range(self.W):if self.mod:self.matrix[i][j]=pow(self.matrix[i][j],other.matrix[i][j],self.mod)else:self.matrix[i][j]=pow(self.matrix[i][j],other.matrix[i][j])else:for i in range(self.H):for j in range(self.W):if self.mod:self.matrix[i][j]=pow(self.matrix[i][j],other,self.mod)else:self.matrix[i][j]=pow(self.matrix[i][j],other)return selfdef __ilshift__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor i in range(self.H):for j in range(self.W):self.matrix[i][j]<<=other.matrix[i][j]else:for i in range(self.H):for j in range(self.W):self.matrix[i][j]<<=otherreturn selfdef __irshift__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor i in range(self.H):for j in range(self.W):self.matrix[i][j]>>=other.matrix[i][j]else:for i in range(self.H):for j in range(self.W):self.matrix[i][j]>>=otherreturn selfdef __iand__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor i in range(self.H):for j in range(self.W):self.matrix[i][j]&=other.matrix[i][j]else:for i in range(self.H):for j in range(self.W):self.matrix[i][j]&=otherreturn selfdef __ior__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor i in range(self.H):for j in range(self.W):self.matrix[i][j]|=other.matrix[i][j]else:for i in range(self.H):for j in range(self.W):self.matrix[i][j]|=otherreturn selfdef __ixor__(self,other):if type(other)==Matrix:assert self.H==other.Hassert self.W==other.Wfor i in range(self.H):for j in range(self.W):self.matrix[i][j]^=other.matrix[i][j]else:for i in range(self.H):for j in range(self.W):self.matrix[i][j]^=otherreturn selfdef __neg__(self):if self.mod:nega=Matrix(matrix=[[(-self.matrix[i][j])%self.mod for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)else:nega=Matrix(matrix=[[-self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)return negadef __pos__(self):posi=Matrix(matrix=[[self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)return posidef __invert__(self):inve=Matrix(matrix=[[~self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)return invedef __abs__(self):abso=Matrix(matrix=[[abs(self.matrix[i][j]) for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)return absodef __getitem__(self,i):if type(i)==int:return self.matrix[i]elif type(i)==tuple:i,j=iif type(i)==int:i=slice(i,i+1)if type(j)==int:j=slice(j,j+1)return Matrix(matrix=[lst[j] for lst in self.matrix[i]],eps=self.eps,mod=self.mod)def __contains__(self,x):for i in range(self.H):if x in self.matrix[i]:return Truereturn Falsedef __str__(self):digit=[max(len(str(self.matrix[i][j])) for i in range(self.H)) for j in range(self.W)]return "\n".join([(" [" if i else "[[")+", ".join([str(self.matrix[i][j]).rjust(digit[j]," ") for j in range(self.W)])+"]" for i in range(self.H)])+"]"def __bool__(self):return Truedef Transpose(self):return Matrix(matrix=[[self.matrix[i][j] for i in range(self.H)] for j in range(self.W)])def Trace(self):assert self.H==self.Wtrace=sum(self.matrix[i][i] for i in range(self.H))if self.mod:trace%=self.modreturn tracedef Elem_Raw_Operate_1(self,i0,i1):self.matrix[i0],self.matrix[i1]=self.matrix[i1],self.matrix[i0]def Elem_Raw_Operate_2(self,i,c):if self.mod:self.matrix[i]=[self.matrix[i][j]*c%self.mod for j in range(self.W)]else:self.matrix[i]=[self.matrix[i][j]*c for j in range(self.W)]def Elem_Raw_Operate_3(self,i0,i1,c):if self.mod:self.matrix[i0]=[(self.matrix[i0][j]+c*self.matrix[i1][j])%self.mod for j in range(self.W)]else:self.matrix[i0]=[self.matrix[i0][j]+c*self.matrix[i1][j] for j in range(self.W)]def Elimination(self,determinant=False,inverse_matrix=False,linear_equation=False,rank=False,upper_triangular=False):h=0ut=Matrix(matrix=[[self.matrix[i][j] for j in range(self.W)] for i in range(self.H)],eps=self.eps,mod=self.mod)if determinant or inverse_matrix:assert self.H==self.Wdet=1if inverse_matrix:assert self.H==self.Wim=Matrix(H=self.H,eps=self.eps,mod=self.mod,identity=1)if linear_equation:assert self.H==linear_equation.Hle=Matrix(matrix=[[linear_equation.matrix[i][j] for j in range(linear_equation.W)] for i in range(linear_equation.H)],eps=self.eps,mod=self.mod)for j in range(ut.W):for i in range(h,ut.H):if abs(ut.matrix[i][j])>ut.eps:if determinant or inverse_matrix:det*=ut.matrix[i][j]if self.mod:det%=self.modif self.mod:inve=MOD(self.mod).Pow(ut.matrix[i][j],-1)else:inve=1/ut.matrix[i][j]ut.Elem_Raw_Operate_1(i,h)if determinant and i!=h and self.mod:det=(-det)%self.modif inverse_matrix:im.Elem_Raw_Operate_1(i,h)if linear_equation:le.Elem_Raw_Operate_1(i,h)ut.Elem_Raw_Operate_2(h,inve)if inverse_matrix:im.Elem_Raw_Operate_2(h,inve)if linear_equation:le.Elem_Raw_Operate_2(h,inve)for ii in range(ut.H):if ii==h:continuex=-ut.matrix[ii][j]ut.Elem_Raw_Operate_3(ii,h,x)if inverse_matrix:im.Elem_Raw_Operate_3(ii,h,x)if linear_equation:le.Elem_Raw_Operate_3(ii,h,x)h+=1breakelse:det=0if linear_equation and any(le[i][0] for i in range(h,self.H)):le=Nonetpl=()if determinant:tpl+=(det,)if inverse_matrix:if det==0:im=Nonetpl+=(im,)if linear_equation:tpl+=(le,)if rank:tpl+=(h,)if upper_triangular:tpl+=(ut,)if len(tpl)==1:tpl=tpl[0]return tpldef Extended_Euclid(n,m):stack=[]while m:stack.append((n,m))n,m=m,n%mif n>=0:x,y=1,0else:x,y=-1,0for i in range(len(stack)-1,-1,-1):n,m=stack[i]x,y=y,x-(n//m)*yreturn x,yclass MOD:def __init__(self,p,e=None):self.p=pself.e=eif self.e==None:self.mod=self.pelse:self.mod=self.p**self.edef Pow(self,a,n):a%=self.modif n>=0:return pow(a,n,self.mod)else:#assert math.gcd(a,self.mod)==1x=Extended_Euclid(a,self.mod)[0]return pow(x,-n,self.mod)def Build_Fact(self,N):assert N>=0self.factorial=[1]if self.e==None:for i in range(1,N+1):self.factorial.append(self.factorial[-1]*i%self.mod)else:self.cnt=[0]*(N+1)for i in range(1,N+1):self.cnt[i]=self.cnt[i-1]ii=iwhile ii%self.p==0:ii//=self.pself.cnt[i]+=1self.factorial.append(self.factorial[-1]*ii%self.mod)self.factorial_inve=[None]*(N+1)self.factorial_inve[-1]=self.Pow(self.factorial[-1],-1)for i in range(N-1,-1,-1):ii=i+1while ii%self.p==0:ii//=self.pself.factorial_inve[i]=(self.factorial_inve[i+1]*ii)%self.moddef Build_Inverse(self,N):self.inverse=[None]*(N+1)assert self.p>Nself.inverse[1]=1for n in range(2,N+1):if n%self.p==0:continuea,b=divmod(self.mod,n)self.inverse[n]=(-a*self.inverse[b])%self.moddef Inverse(self,n):return self.inverse[n]def Fact(self,N):if N<0:return 0retu=self.factorial[N]if self.e!=None and self.cnt[N]:retu*=pow(self.p,self.cnt[N],self.mod)%self.modretu%=self.modreturn retudef Fact_Inve(self,N):if self.e!=None and self.cnt[N]:return Nonereturn self.factorial_inve[N]def Comb(self,N,K,divisible_count=False):if K<0 or K>N:return 0retu=self.factorial[N]*self.factorial_inve[K]%self.mod*self.factorial_inve[N-K]%self.modif self.e!=None:cnt=self.cnt[N]-self.cnt[N-K]-self.cnt[K]if divisible_count:return retu,cntelse:retu*=pow(self.p,cnt,self.mod)retu%=self.modreturn retuN,M=map(int,readline().split())A,B,Y=[],[],[]for m in range(M):A.append(int(readline()))B.append([b-1 for b in map(int,readline().split())])Y.append(int(readline()))ans_lst=[0]*Nfor c in range(31):Mat=[[0]*N for m in range(M)]for m in range(M):for b in B[m]:Mat[m][b]=1Mat_Y=[[Y[m]>>c&1] for m in range(M)]Mat=Matrix(matrix=Mat,mod=2)Mat_Y=Matrix(matrix=Mat_Y,mod=2)X=Mat.Elimination(linear_equation=Mat_Y)if X==None:print(-1)exit()for m in range(M):ans_lst[m]|=X[m][0]<<cprint(*ans_lst,sep="\n")