#985957 (PyPy3) No.2907 Business Revealing Dora Tiles

提出ソース

結果

問題	No.2907 Business Revealing Dora Tiles
ユーザー	👑 獅子座じゃない人
提出日時	2024-06-06 14:42:33
言語	PyPy3 (7.3.15)
結果	TLE
実行時間	-
コード長	7,434 bytes
コンパイル時間	5,465 ms
コンパイル使用メモリ	82,448 KB
実行使用メモリ	114,584 KB
最終ジャッジ日時	2024-09-23 12:00:41
合計ジャッジ時間	74,707 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	84 ms 84,792 KB
testcase_01	AC	81 ms 77,480 KB
testcase_02	AC	81 ms 77,520 KB
testcase_03	AC	102 ms 77,752 KB
testcase_04	AC	104 ms 77,900 KB
testcase_05	AC	143 ms 78,564 KB
testcase_06	AC	170 ms 79,508 KB
testcase_07	AC	82 ms 77,664 KB
testcase_08	AC	85 ms 77,532 KB
testcase_09	AC	157 ms 79,776 KB
testcase_10	AC	84 ms 77,952 KB
testcase_11	AC	2,856 ms 92,840 KB
testcase_12	AC	94 ms 77,880 KB
testcase_13	AC	94 ms 78,080 KB
testcase_14	AC	103 ms 78,188 KB
testcase_15	AC	236 ms 80,528 KB
testcase_16	AC	84 ms 77,604 KB
testcase_17	AC	97 ms 77,896 KB
testcase_18	AC	821 ms 85,180 KB
testcase_19	AC	105 ms 77,808 KB
testcase_20	AC	88 ms 77,748 KB
testcase_21	AC	2,750 ms 91,472 KB
testcase_22	AC	224 ms 80,768 KB
testcase_23	AC	456 ms 84,276 KB
testcase_24	AC	2,202 ms 109,064 KB
testcase_25	AC	2,218 ms 110,020 KB
testcase_26	AC	2,465 ms 113,176 KB
testcase_27	AC	2,362 ms 110,948 KB
testcase_28	AC	2,136 ms 106,892 KB
testcase_29	AC	2,319 ms 112,792 KB
testcase_30	AC	2,323 ms 110,612 KB
testcase_31	AC	2,269 ms 110,128 KB
testcase_32	AC	2,349 ms 114,204 KB
testcase_33	AC	2,106 ms 108,568 KB
testcase_34	AC	2,122 ms 108,536 KB
testcase_35	AC	1,388 ms 92,220 KB
testcase_36	AC	2,258 ms 109,724 KB
testcase_37	AC	2,254 ms 106,636 KB
testcase_38	AC	2,418 ms 114,584 KB
testcase_39	AC	2,246 ms 109,260 KB
testcase_40	AC	2,209 ms 110,612 KB
testcase_41	AC	1,372 ms 92,052 KB
testcase_42	AC	2,221 ms 109,552 KB
testcase_43	AC	2,296 ms 112,956 KB
testcase_44	TLE	-
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	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

from collections import deque
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_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(i+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(i+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 dynamic_matrix_rank(rank: int, a_col: int, from_col: int, to_col: int, u: list[list[int]], m: list[list[int]]) -> int:
    v=[0]*rank
    for i in range(rank):
        v[i]=m[i][from_col]^m[i][to_col]
    v2=[0]*rank
    for i in range(rank):
        for j in range(rank):
            v2[i]^=nim_product(u[i][j], v[j])
    if v2[a_col]==1:
        return 0
    clean=[0]*rank
    inv=nim_inv(v2[a_col]^1)
    for i in range(rank):
        if i==a_col:
            clean[i]=inv ^ 1
        else:
            clean[i]=nim_product(v2[i], inv)
    u_row=u[a_col][:]
    for i in range(rank):
        for j in range(rank):
            u[i][j]^=nim_product(clean[i], u_row[j])
    return 1

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, members, not_members=gauss_jordan(t, n, h)
s=sum(1 << i for i in members)
seen=[0]*(1<<n)
ranks=[0]*(1<<n)
seen[s]=1
ranks[s]=rank
u=[[int(i==j) for j in range(rank)] for i in range(rank)]
stack=deque[tuple[int, int]]()
stack.append((s+(1<<n), n*(1<<n)))
stack.append((s, n*(1<<n)))
while stack:
    s, ij=stack.pop()
    i=ij>>n
    j=ij-(i<<n)
    if s<(1<<n):
        if i<n:
            if dynamic_matrix_rank(rank, i, members[i], not_members[j], u, h):
                ranks[s]=rank
                members[i],not_members[j]=not_members[j],members[i]
            else:
                continue
        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]=1
                stack.append((new_s+(1<<n), i*(1<<n)+j))
                stack.append((new_s, i*(1<<n)+j))
    else:
        s-=1<<n
        if i<n and ranks[s]>0:
            members[i],not_members[j]=not_members[j],members[i]
            dynamic_matrix_rank(rank, i, members[i], not_members[j], u, h)
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)

yukicoder

結果

テストケース

ソースコード