結果

問題 No.2907 Business Revealing Dora Tiles
ユーザー 👑 amentorimaruamentorimaru
提出日時 2024-06-01 14:36:48
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,502 bytes
コンパイル時間 5,648 ms
コンパイル使用メモリ 81,988 KB
実行使用メモリ 102,180 KB
最終ジャッジ日時 2024-09-23 11:20:46
合計ジャッジ時間 18,930 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 166 ms
96,424 KB
testcase_01 AC 154 ms
89,344 KB
testcase_02 AC 148 ms
89,316 KB
testcase_03 AC 242 ms
91,640 KB
testcase_04 AC 300 ms
92,296 KB
testcase_05 AC 314 ms
92,504 KB
testcase_06 AC 546 ms
95,236 KB
testcase_07 AC 187 ms
89,024 KB
testcase_08 AC 159 ms
88,980 KB
testcase_09 AC 428 ms
93,308 KB
testcase_10 AC 184 ms
89,648 KB
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
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 # 

import sys
from fractions import Fraction
input = sys.stdin.readline
def read_values(): return tuple(map(int, input().split()))
def read_list(): return list(read_values())

class Nimber():
    def __init__(self, loglog_small_product = 3, loglog_small_inv = 3, loglog_siz = 6):        
        self.loglog_siz = loglog_siz
        self.siz = 1 << (1 << loglog_siz)
        self.loglog_small_product = loglog_small_product
        self.fill_small_product(loglog_small_product)
        self.loglog_small_inv = loglog_small_inv
        self.fill_small_inv(loglog_small_inv)
        
    def fill_small_product(self, loglog_small):
        log_small = 1 << loglog_small
        self.small_product = [[0] * (1 << log_small) for _ in range(1 << log_small)]
        for a in range(1, 1 << log_small):
            self.small_product[a][1] = a
            self.small_product[1][a] = a
            
            d = log_small // 2
            while a < (1 << d):
                d >>= 1
            for b in range(2, a + 1):
                a1, a2 = a >> d, a & ((1 << d) - 1)    
                b1, b2 = b >> d, b & ((1 << d) - 1)    
                ab1 = self.small_product[a1][b1]
                ab2 = self.small_product[a2][b2]
                ab3 = self.small_product[a1 ^ a2][b1 ^ b2]
                res = self.small_product[ab1][1 << (d - 1)] ^ ab2 ^ ((ab2 ^ ab3) << d)
                self.small_product[a][b] = res
                self.small_product[b][a] = res
       
    def fill_small_inv(self, loglog_small):
        log_small = 1 << loglog_small
        self.small_inv = [0] * (1 << log_small)
        for i in range(1,1<<log_small):
            for j in range(1,1<<log_small):
                if self.small_product[i][j] == 1:
                    self.small_inv[i] = j
                    break

    def product_impl(self, a, b, loglog):
        if loglog <= self.loglog_small_product:
            return self.small_product[a][b]
        if max(a,b) <= 1:
            return a * b
        us = 1 << (loglog - 1)
        assert(a < (1 << (1 << loglog)) and b < (1 << (1 << loglog)))
        lm = (1 << us) - 1        
        ab1 = self.product_impl(a >> us, b >> us, loglog - 1)
        ab2 = self.product_impl(a & lm, b & lm, loglog - 1)
        ab3 = self.product_impl((a & lm) ^ (a >> us), (b & lm) ^ (b >> us), loglog - 1)
        res = ab3 ^ ab2
        res <<= us
        res ^= ab2
        res ^= self.product_impl(1 << (us - 1), ab1, loglog - 1)
        return res

    def product(self, a, b):
        assert(0 <= a < self.siz and 0 <= b < self.siz)
        return self.product_impl(a, b, self.loglog_siz)
    
    def inv_impl(self, a, loglog):
        if a < len(self.small_inv):
            return self.small_inv[a] 
        p = 1 << (loglog - 1)
        assert(a < (1<<(1<<loglog)))
        ah = a >> p
        al = a - (ah << p)
        a2 = self.product_impl(ah ^ al, al, loglog)
        ahsq = self.product_impl(ah, ah, loglog - 1)
        a3 = self.product_impl(ahsq, 1 << (p - 1), loglog - 1)
        half = self.inv_impl(a2 ^ a3, loglog - 1)
        return (self.product_impl(half, ah, loglog - 1) << p) ^ (self.product_impl(half, ah ^ al, loglog))
    
    def inv(self, a):
        assert(0 <= a < self.siz)
        for p in range(self.loglog_siz + 1):
            if a < (1 << (1 << p)):
                return self.inv_impl(a, p)
        

def main():  
    nimber = Nimber()
    n,t = read_values()
    h = [read_list() for _ in range(t)]
    for i in range(t):
        for j in range(n):
            h[i][j] -= 1        
    mod = 998244353
    tp = (1 << 64) % mod
    ans = 0
    bn = 1 << n
    for b in range(bn):
        use = 0
        add = 1
        for j in range(n):
            if (b >> j) & 1:
                continue
            idx = -1
            for i in range(t):
                if (use >> i) & 1 == 0 and h[i][j] != 0:
                    idx = i                    
                    inv = nimber.inv(h[i][j])
                    break
            if idx == -1:
                add *= tp
                add %= mod
                continue
            use |= 1 << i
            for i in range(t):
                if i != idx and h[i][j] != 0:
                    mul = nimber.product(inv, h[i][j])
                    for jj in range(n):
                        h[i][jj] ^= nimber.product(mul, h[idx][jj])
        ans += add if int.bit_count(b) % 2 == 0 else -add
        ans %= mod
    print(ans)
        
if __name__ == "__main__":
    main()
0