結果

問題 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
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 82 ms
73,988 KB
testcase_01 AC 58 ms
67,860 KB
testcase_02 AC 57 ms
67,948 KB
testcase_03 WA -
testcase_04 AC 103 ms
78,436 KB
testcase_05 WA -
testcase_06 AC 126 ms
78,284 KB
testcase_07 AC 59 ms
67,024 KB
testcase_08 AC 83 ms
68,024 KB
testcase_09 AC 134 ms
78,492 KB
testcase_10 AC 66 ms
72,784 KB
testcase_11 WA -
testcase_12 AC 80 ms
77,456 KB
testcase_13 AC 87 ms
77,436 KB
testcase_14 AC 120 ms
79,104 KB
testcase_15 WA -
testcase_16 AC 60 ms
68,676 KB
testcase_17 AC 83 ms
77,428 KB
testcase_18 WA -
testcase_19 AC 89 ms
77,436 KB
testcase_20 AC 66 ms
71,980 KB
testcase_21 WA -
testcase_22 AC 189 ms
79,224 KB
testcase_23 AC 443 ms
83,424 KB
testcase_24 TLE -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
testcase_53 -- -
testcase_54 -- -
testcase_55 -- -
testcase_56 -- -
testcase_57 -- -
testcase_58 -- -
testcase_59 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #

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)
0