結果
問題 | No.2907 Business Revealing Dora Tiles |
ユーザー |
👑 ![]() |
提出日時 | 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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 TLE * 2 -- * 10 |
ソースコード
import sysfrom collections import Counterinput = sys.stdin.readlinedef read_values(): return map(int, input().split())def read_list(): return list(read_values())mod=998244353pre_prod = [[0] * 256 for _ in range(256)]pre_inv = [0] * 256def nim_product(a,b,d=6):if min(a,b) <= 1:return a*bif a < 256 and b < 256 and pre_prod[a][b]:return pre_prod[a][b]d -= 1d_pow = 1 << dd_pow_pow = 1 << d_powif a < d_pow_pow and b < d_pow_pow:return nim_product(a,b,d)au = a >> d_powal = a - (au << d_pow)bu = b >> d_powbl = 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] = respre_prod[b][a] = resreturn resdef nim_product_inv(a,d=6):if a<256:return pre_inv[a]d -= 1d_pow = 1 << dif a < (1<<d_pow):return nim_product_inv(a,d)au = a >> d_powal = 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]=bpre_inv[b]=an,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]*tfor c0 in range(n-1,-1,-1):for r in range(t):if h[r][c0]==0 or use[r] != -1:continueuse[r]=c0r0=rbreakelse:continueinv = 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:continuefor 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=0mul=pow(2,64,mod)def dfs(a, add, pop, column):nonlocal ansif column < 0:if pop%2:ans-=addelse:ans+=addans%=modreturna0=[r[:column] for r in a[:column]]add0=addif a[-1][-1]==0:add0*=muladd0%=moddfs(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])breakdfs(a0,add,pop+1,column-1)dfs(base_a,1,0,n-1)print(ans%mod)if __name__ == "__main__":main()