結果

問題 No.2907 Business Revealing Dora Tiles
コンテスト
ユーザー amentorimaru
提出日時 2024-06-01 13:50:32
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,470 bytes
コンパイル時間 5,463 ms
コンパイル使用メモリ 82,212 KB
実行使用メモリ 108,404 KB
最終ジャッジ日時 2024-09-23 11:08:21
合計ジャッジ時間 19,069 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 TLE * 1 -- * 48
権限があれば一括ダウンロードができます

ソースコード

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 = 4, 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, 3, 2]
        lls = 2
        for a in range(4, 1 << log_small):
            if a >= (1 << (1 << lls)):
                lls += 1
            self.small_inv.append(self.inv_impl(a, lls))

    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