結果
| 問題 |
No.2907 Business Revealing Dora Tiles
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2024-06-03 10:39:50 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,809 bytes |
| コンパイル時間 | 5,733 ms |
| コンパイル使用メモリ | 82,412 KB |
| 実行使用メモリ | 154,292 KB |
| 最終ジャッジ日時 | 2024-09-23 11:26:48 |
| 合計ジャッジ時間 | 28,833 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 15 WA * 6 TLE * 1 -- * 35 |
ソースコード
from copy import deepcopy
from collections import deque
from itertools import combinations
nim_prod_table=[[0]*256 for _ in range(256)]
nim_inv_table=[0]*256
def nim_prod_and_inv_precalc():
nim_prod_table[0][0]=0
nim_prod_table[0][1]=0
nim_prod_table[1][0]=0
nim_prod_table[1][1]=1
nim_inv_table[1]=1
for d in range(3):
p=1<<d
for a in range(1<<(2*p)):
for b in range(1<<p, 1<<(2*p)):
a_h=a>>p
a_l=a-(a_h<<p)
b_h=b>>p
b_l=b-(b_h<<p)
al_bl=nim_prod_table[a_l][b_l]
ahl_bhl=nim_prod_table[a_h^a_l][b_h^b_l]
ah_bh=nim_prod_table[a_h][b_h]
ah_bh_h=nim_prod_table[ah_bh][1<<(p-1)]
nim_prod_table[a][b]=nim_prod_table[b][a]=((al_bl^ahl_bhl)<<p)^(al_bl^ah_bh_h)
if nim_prod_table[a][b]==1:
nim_inv_table[a]=b
nim_inv_table[b]=a
def nim_product(a: int, b: int, p: int=64) -> int:
if p==64:
if a<(1<<8) and b<(1<<8):
p=8
elif a<(1<<16) and b<(1<<16):
p=16
elif a<(1<<32) and b<(1<<32):
p=32
if p==8:
return nim_prod_table[a][b]
p//=2
a_h=a>>p
a_l=a-(a_h<<p)
b_h=b>>p
b_l=b-(b_h<<p)
al_bl=nim_product(a_l, b_l, p)
ahl_bhl=nim_product(a_h^a_l, b_h^b_l)
ah_bh=nim_product(a_h, b_h, p)
ah_bh_h=nim_product(ah_bh, 1<<(p-1))
return ((al_bl^ahl_bhl)<<p)^(al_bl^ah_bh_h)
def nim_inv(a: int, p: int=64) -> int:
if p==64:
if a<(1<<8):
p=8
elif a<(1<<16):
p=16
elif a<(1<<32):
p=32
if p==8:
return nim_inv_table[a]
p//=2
a_h=a>>p
a_l=a-(a_h<<p)
half_inv=nim_inv(nim_product(a_h^a_l, a_l)^nim_product(nim_product(a_h, a_h), 1<<(p-1)), p)
return (nim_product(half_inv, a_h)<<p)^nim_product(half_inv, a_h^a_l)
def gauss_jordan(r: int, c: int, m: list[list[int]]) -> tuple[int, list[int], list[int]]:
members=[]
not_members=[]
rank=0
for i in range(c):
pivot=-1
for j in range(rank, r):
if m[j][i]>0:
pivot=j
break
if pivot==-1:
not_members.append(i)
continue
members.append(i)
m[pivot], m[rank]=m[rank], m[pivot]
inv=nim_inv(m[rank][i])
m[rank][i]=1
for k in range(rank+1, c):
m[rank][k]=nim_product(m[rank][k], inv)
for j in range(r):
if j==rank:
continue
factor=m[j][i]
m[j][i]=0
for k in range(rank+1, c):
m[j][k]^=nim_product(m[rank][k], factor)
rank+=1
if rank==r:
not_members+=[j for j in range(i+1, c)]
break
return rank, members, not_members
def clean_column(rank: int, d: list[list[int]], u: list[list[int]], row: int, col: int):
inv=nim_inv(d[row][col])
v=[(inv^1) if i==row else nim_product(d[i][col], inv) for i in range(rank)]
new_d=deepcopy(d)
new_u=deepcopy(u)
for i in range(rank):
for j in range(rank):
new_d[i][j]^=nim_product(v[i], d[row][j])
new_u[i][j]^=nim_product(v[i], u[row][j])
d, new_d=new_d, d
def dynamic_matrix_rank(rank: int, a_col: int, m_col: int, u: list[list[int]], a: list[list[int]], m: list[list[int]]) -> bool:
v=[(a[i][a_col]^m[i][m_col]) for i in range(rank)]
new_v=[0]*rank
for i in range(rank):
for j in range(rank):
new_v[i]^=nim_product(u[i][j], v[j])
d=[[int(i==j) for j in range(rank)] for i in range(rank)]
leading_entry_row=rank
for i in range(rank):
d[i][a_col]^=new_v[i]
if i>=a_col and leading_entry_row==rank and d[i][a_col]>0:
leading_entry_row=i
if leading_entry_row<rank:
clean_column(rank, d, u, leading_entry_row, a_col)
leading_entry_col=rank
for i in range(a_col):
if a[a_col][i]>0:
leading_entry_col=i
break
if leading_entry_col<rank:
clean_column(rank, d, u, a_col, leading_entry_col)
for i in range(rank):
ok=False
for j in range(i, rank):
if d[j][i]>0:
if i!=j:
d[i], d[j]=d[j], d[i]
u[i], u[j]=u[j], u[i]
ok=True
break
if not ok:
return False
return True
nim_prod_and_inv_precalc()
n,t=map(int, input().split())
h=[list(map(lambda a: int(a)-1, input().split())) for _ in range(t)]
rank, members, not_members=gauss_jordan(t, n, h)
s=0
for i in members:
s+=1<<i
seen=[False]*(1<<n)
ranks=[0]*(1<<n)
stack=deque[tuple[int, list[int], list[int], list[list[int]], list[list[int]]]]()
seen[s]=True
ranks[s]=rank
e=[[int(i==j) for j in range(rank)] for i in range(rank)]
stack.append((s, members, not_members, e, e))
while stack:
s, members, not_members, u, a=stack.pop()
for i in range(len(members)):
for j in range(len(not_members)):
new_s=s-(1<<members[i])+(1<<not_members[j])
if seen[new_s]:
continue
seen[new_s]=True
new_u=deepcopy(u)
new_a=deepcopy(a)
if dynamic_matrix_rank(rank, i, not_members[j], new_u, new_a, h):
new_members=deepcopy(members)
new_not_members=deepcopy(not_members)
new_members[i], new_not_members[j]=new_not_members[j], new_members[i]
ranks[new_s]=rank
stack.append((new_s, new_members, new_not_members, new_u, new_a))
for r in reversed(range(rank)):
for members_tuple in combinations(range(n), r):
members=list(members_tuple)
is_member=[False]*n
s=0
for i in members:
is_member[i]=True
s+=1<<i
for i in range(n):
if is_member[i]:
continue
if ranks[s+(1<<i)]>0:
ranks[s]=r
break
for r in range(n):
for members_tuple in combinations(range(n), r):
members=list(members_tuple)
is_member=[False]*n
s=0
for i in members:
is_member[i]=True
s+=1<<i
for i in range(n):
if is_member[i]:
continue
ranks[s+(1<<i)]=max(ranks[s], ranks[s+(1<<i)])
ans=0
P=932051910
MOD=998244353
for s in range(1<<n):
count=s.bit_count()
if n%2>0:
if count%2>0:
ans+=pow(P, count-ranks[s], MOD)
else:
ans-=pow(P, count-ranks[s], MOD)
else:
if count%2>0:
ans-=pow(P, count-ranks[s], MOD)
else:
ans+=pow(P, count-ranks[s], MOD)
ans%=MOD
print(ans)