結果

問題 No.2907 Business Revealing Dora Tiles
ユーザー 👑 獅子座じゃない人獅子座じゃない人
提出日時 2024-06-07 10:37:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 5,871 bytes
コンパイル時間 6,068 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 100,728 KB
最終ジャッジ日時 2024-09-23 12:17:54
合計ジャッジ時間 72,881 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 87 ms
77,472 KB
testcase_01 AC 75 ms
77,252 KB
testcase_02 AC 71 ms
77,232 KB
testcase_03 AC 85 ms
77,508 KB
testcase_04 AC 93 ms
77,276 KB
testcase_05 AC 87 ms
77,400 KB
testcase_06 AC 139 ms
79,332 KB
testcase_07 AC 113 ms
77,232 KB
testcase_08 AC 68 ms
77,392 KB
testcase_09 AC 90 ms
77,524 KB
testcase_10 AC 76 ms
77,260 KB
testcase_11 AC 1,590 ms
89,008 KB
testcase_12 AC 86 ms
77,404 KB
testcase_13 AC 103 ms
77,788 KB
testcase_14 AC 104 ms
78,180 KB
testcase_15 AC 166 ms
79,576 KB
testcase_16 AC 73 ms
77,204 KB
testcase_17 AC 88 ms
77,624 KB
testcase_18 AC 580 ms
83,020 KB
testcase_19 AC 86 ms
77,792 KB
testcase_20 AC 81 ms
77,460 KB
testcase_21 AC 1,235 ms
86,496 KB
testcase_22 AC 204 ms
79,816 KB
testcase_23 AC 405 ms
82,256 KB
testcase_24 AC 2,427 ms
96,796 KB
testcase_25 AC 2,420 ms
97,604 KB
testcase_26 AC 2,581 ms
98,016 KB
testcase_27 AC 2,592 ms
97,256 KB
testcase_28 AC 2,351 ms
93,148 KB
testcase_29 AC 2,509 ms
97,500 KB
testcase_30 AC 2,471 ms
99,024 KB
testcase_31 AC 2,566 ms
96,092 KB
testcase_32 AC 2,646 ms
98,268 KB
testcase_33 AC 2,398 ms
94,560 KB
testcase_34 AC 2,488 ms
97,504 KB
testcase_35 AC 2,471 ms
99,432 KB
testcase_36 AC 2,407 ms
94,556 KB
testcase_37 AC 2,360 ms
95,064 KB
testcase_38 AC 2,493 ms
96,084 KB
testcase_39 AC 2,495 ms
95,836 KB
testcase_40 AC 2,468 ms
94,796 KB
testcase_41 AC 2,608 ms
95,432 KB
testcase_42 AC 2,479 ms
99,284 KB
testcase_43 AC 2,499 ms
98,140 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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)]
for i in range(t):
    h[i].reverse()
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)
0