結果
問題 |
No.2907 Business Revealing Dora Tiles
|
ユーザー |
|
提出日時 | 2024-06-06 14:58:52 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 5,833 bytes |
コンパイル時間 | 5,744 ms |
コンパイル使用メモリ | 81,772 KB |
実行使用メモリ | 100,740 KB |
最終ジャッジ日時 | 2024-09-23 12:04:40 |
合計ジャッジ時間 | 75,466 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 TLE * 1 -- * 15 |
ソースコード
from itertools import combinations nim_prod_table=[[0]*256 for _ in range(256)] nim_inv_table=[0]*65536 def nim_prod_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_power(a: int, n: int, p: int=64) -> int: if p==64: if a<(1<<8) and n<8: p=8 elif a<(1<<16) and n<16: p=16 elif a<(1<<32) and n<32: p=32 if p==8: return nim_prod_table[a][1<<n] p//=2 a_h=a>>p a_l=a-(a_h<<p) if n<p: return (nim_product_power(a_h, n, p)<<p)^nim_product_power(a_l, n, p) else: n-=p return (nim_product_power(a_h^a_l, n, p)<<p)^nim_product_power(nim_product_power(a_h, n, p), p-1, p) def nim_square(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_prod_table[a][a] p//=2 a_h=a>>p a_l=a-(a_h << p) h_sq=nim_square(a_h, p) l_sq=nim_square(a_l, p) return (h_sq<<p)^nim_product_power(h_sq, p-1, p)^l_sq def nim_product(a: int, b: int, p: int=64) -> int: if a==0 or b==0: return 0 if a==1: return b if b==1: return a 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, p) ah_bh=nim_product(a_h, b_h, p) ah_bh_h=nim_product_power(ah_bh, p-1, p) return ((al_bl^ahl_bhl)<<p)^(al_bl^ah_bh_h) def nim_inv_precalc(): for a in range(1<<8, 1<<16): p=8 a_h=a>>p a_l=a-(a_h<<p) half_inv=nim_inv_table[nim_product(a_h^a_l, a_l, p)^nim_product_power(nim_square(a_h, p), p-1, p)] nim_inv_table[a]=(nim_product(half_inv, a_h, p)<<p)^nim_product(half_inv, a_h^a_l, p) def nim_inv(a: int, p: int=64) -> int: if p==64: if a<(1<<16): p=16 elif a<(1<<32): p=32 if p==16: 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, p)^nim_product_power(nim_square(a_h, p), p-1, p), p) return (nim_product(half_inv, a_h, p)<<p)^nim_product(half_inv, a_h^a_l, p) def gauss(r: int, c: int, m: list[list[int]], exists: list[int]) -> int: rank=0 for i in range(c): if not exists[i]: continue pivot=-1 for j in range(rank, r): if m[j][i]>0: pivot=j break if pivot==-1: continue m[pivot], m[rank]=m[rank], m[pivot] if rank==r-1: rank+=1 break inv=nim_inv(m[rank][i]) m[rank][i]=1 for k in range(0, c): if k==i: continue 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(0, c): if k==i: continue m[j][k]^=nim_product(m[rank][k], factor) rank+=1 return rank nim_prod_precalc() nim_inv_precalc() n,t=map(int, input().split()) h=[list(map(lambda a: int(a)-1, input().split())) for _ in range(t)] rank=gauss(t, n, h, [1]*n) ranks=[0]*(1<<n) for members_tuple in combinations(range(n), rank): members=list(members_tuple) is_member=[0]*n s=0 for i in members: is_member[i]=1 s+=1<<i if gauss(rank, n, h, is_member)==rank: ranks[s]=rank for r in reversed(range(rank)): for members_tuple in combinations(range(n), r): members=list(members_tuple) is_member=[0]*n s=0 for i in members: is_member[i]=1 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=[0]*n s=0 for i in members: is_member[i]=1 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 mods=[1, 932051910, 299560064, 268998206, 169907034, 617122664, 934978948, 751815647, 60241440, 910883406, 623687709, 299771973, 824242875, 286857587, 12424206, 89078497, 595200811, 971438438, 608817788, 778210505, 170380535] MOD=998244353 for s in range(1<<n): count=s.bit_count() if n%2>0: if count%2>0: ans+=mods[count-ranks[s]] else: ans-=mods[count-ranks[s]] else: if count%2>0: ans-=mods[count-ranks[s]] else: ans+=mods[count-ranks[s]] ans%=MOD print(ans)