結果
問題 | No.2907 Business Revealing Dora Tiles |
ユーザー | 👑 amentorimaru |
提出日時 | 2024-09-17 01:35:09 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,381 bytes |
コンパイル時間 | 5,852 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 129,684 KB |
最終ジャッジ日時 | 2024-09-23 13:11:32 |
合計ジャッジ時間 | 67,760 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 639 ms
93,584 KB |
testcase_01 | AC | 585 ms
86,256 KB |
testcase_02 | AC | 588 ms
86,412 KB |
testcase_03 | AC | 607 ms
86,508 KB |
testcase_04 | AC | 636 ms
86,896 KB |
testcase_05 | AC | 621 ms
86,780 KB |
testcase_06 | AC | 727 ms
88,312 KB |
testcase_07 | AC | 654 ms
86,148 KB |
testcase_08 | AC | 604 ms
86,772 KB |
testcase_09 | AC | 630 ms
86,792 KB |
testcase_10 | AC | 607 ms
86,384 KB |
testcase_11 | AC | 1,291 ms
95,240 KB |
testcase_12 | AC | 615 ms
87,048 KB |
testcase_13 | AC | 610 ms
86,764 KB |
testcase_14 | AC | 636 ms
86,892 KB |
testcase_15 | AC | 636 ms
87,288 KB |
testcase_16 | AC | 592 ms
86,404 KB |
testcase_17 | AC | 628 ms
86,524 KB |
testcase_18 | AC | 849 ms
90,732 KB |
testcase_19 | AC | 609 ms
86,664 KB |
testcase_20 | AC | 614 ms
86,636 KB |
testcase_21 | AC | 1,536 ms
98,412 KB |
testcase_22 | AC | 745 ms
89,092 KB |
testcase_23 | AC | 1,016 ms
93,448 KB |
testcase_24 | AC | 1,076 ms
92,396 KB |
testcase_25 | AC | 1,076 ms
94,340 KB |
testcase_26 | AC | 1,103 ms
92,160 KB |
testcase_27 | AC | 1,097 ms
92,264 KB |
testcase_28 | AC | 1,074 ms
91,648 KB |
testcase_29 | AC | 1,079 ms
92,556 KB |
testcase_30 | AC | 1,151 ms
93,556 KB |
testcase_31 | AC | 1,092 ms
92,680 KB |
testcase_32 | AC | 1,094 ms
93,560 KB |
testcase_33 | AC | 1,093 ms
92,140 KB |
testcase_34 | AC | 1,127 ms
92,296 KB |
testcase_35 | AC | 1,072 ms
92,136 KB |
testcase_36 | AC | 1,113 ms
92,656 KB |
testcase_37 | AC | 1,057 ms
91,652 KB |
testcase_38 | AC | 1,084 ms
92,044 KB |
testcase_39 | AC | 1,067 ms
91,888 KB |
testcase_40 | AC | 1,055 ms
92,164 KB |
testcase_41 | AC | 1,129 ms
91,780 KB |
testcase_42 | AC | 1,107 ms
93,568 KB |
testcase_43 | AC | 1,163 ms
92,032 KB |
testcase_44 | AC | 2,786 ms
108,676 KB |
testcase_45 | TLE | - |
testcase_46 | AC | 2,464 ms
104,704 KB |
testcase_47 | AC | 1,988 ms
104,448 KB |
testcase_48 | AC | 1,950 ms
102,664 KB |
testcase_49 | TLE | - |
testcase_50 | -- | - |
testcase_51 | -- | - |
testcase_52 | -- | - |
testcase_53 | -- | - |
testcase_54 | -- | - |
testcase_55 | -- | - |
testcase_56 | -- | - |
testcase_57 | -- | - |
testcase_58 | -- | - |
testcase_59 | -- | - |
ソースコード
import sys from collections import Counter input = sys.stdin.readline def read_values(): return map(int, input().split()) def read_list(): return list(read_values()) mod=998244353 pre_prod = [[0] * 256 for _ in range(256)] pre_inv = [0] * 256 def nim_product(a,b,d=6): if min(a,b) <= 1: return a*b if a < 256 and b < 256 and pre_prod[a][b]: return pre_prod[a][b] d -= 1 d_pow = 1 << d d_pow_pow = 1 << d_pow if a < d_pow_pow and b < d_pow_pow: return nim_product(a,b,d) au = a >> d_pow al = a - (au << d_pow) bu = b >> d_pow bl = b - (bu << d_pow) aubu = nim_product(au,bu,d) ablu = nim_product(au^al,bu^bl,d) albl = nim_product(al,bl,d) res = ((albl ^ ablu) << d_pow) ^ (nim_product(aubu, d_pow_pow // 2, d)) ^ (albl) if a < 256 and b < 256: pre_prod[a][b] = res pre_prod[b][a] = res return res def nim_product_inv(a,d=6): if a<256: return pre_inv[a] d -= 1 d_pow = 1 << d if a < (1<<d_pow): return nim_product_inv(a,d) au = a >> d_pow al = a - (au << d_pow) half_inv = nim_product_inv(nim_product(au ^ al, al, d) ^ nim_product(nim_product(au, au, d), 1 << (d_pow - 1)), d) return (nim_product(half_inv, au, d) << d_pow) ^ nim_product(half_inv, au ^ al, d) def main(): for a in range(1,256): for b in range(1,256): c = nim_product(a,b) if c==1: pre_inv[a]=b pre_inv[b]=a n,t=read_values() h=list() for i in range(t): h.append(read_list()) h[-1] = [v-1 for v in h[-1]] use=[-1]*t for c0 in range(n-1,-1,-1): for r in range(t): if h[r][c0]==0 or use[r] != -1: continue use[r]=c0 r0=r break else: continue inv = nim_product_inv(h[r0][c0]) h[r0] = [nim_product(v,inv) for v in h[r0]] for r in range(t): if r == r0: continue for c in range(n): h[r][c] ^= nim_product(h[r0][c],h[r][c0]) base_a = [[0] * n for _ in range(n)] for i in range(t): if use[i] != -1: base_a[use[i]] = h[i] ans=0 mul=pow(2,64,mod) def dfs(a, add, pop, column): nonlocal ans if column < 0: if pop%2: ans-=add else: ans+=add ans%=mod return a0=[r[:column] for r in a[:column]] add0=add if a[-1][-1]==0: add0*=mul add0%=mod dfs(a0,add0,pop,column-1) for c0 in range(column-1,-1,-1): if a[-1][c0]: ainv = nim_product_inv(a[-1][c0]) ar=[nim_product(ainv,m) for m in a[-1]] for r in range(column): for c in range(column): if r==c0: if a0[r][c0] != ar[c0]: a0[r][c] ^= ar[c] else: a0[r][c] ^= nim_product(ar[c], a0[r][c0]) break dfs(a0,add,pop+1,column-1) dfs(base_a,1,0,n-1) print(ans%mod) if __name__ == "__main__": main()