I decided not to withdraw from NoSub this time and entered the contest, but as a result it was 0 complete. However, this time I didn't say that the consideration was unsatisfactory, and it was a type of problem that I had never done in the first place, so I think it can't be helped. Also, I wanted to solve not only A problem but also C problem, but I couldn't solve it because the last implementation couldn't be completed. It seemed impossible even if I thought about it for a day, so I will skip it once because I am lacking in ability. Articles have been updated lately, so I'll do my best to increase the pace of updates.
The problem is to repeat the operation of replacing (or not replacing) $ x $ with $ x \ oplus A_i $ with $ i = 1 $ ~ $ n $, and finally consider whether it can be set to 0.
Winning or losing is decided in a two-player fighting game, so think about ** what will happen to the final state ** (①). It should also be noted that XOR ** can calculate each bit independently ** (②).
First, I noticed that it is a special case that $ x = 0 $ because all bits are 0. Therefore, I thought that it would be quite difficult to achieve the goal of ** people 0, and decided to explore that case. However, since each bit moves independently from premise (2), I thought that it would be difficult to find it discoveratively, so I rejected this policy.
If $ x = 0 $ is regarded as the state of the value of $ x $, the state of $ x $ in each round $ i $ is at most $ 10 ^ {18} $, so $ m = 10 ^ {18} I thought that if it was $, it could be calculated by $ O (mn) $. Also, when combined with Assumption (1), the person with number 0 thinks of a candidate for the value of $ x $ at the time of round $ i $, which will eventually become $ x = 0 $, and number 1 I wonder if I can make a value of $ x $ that is not a candidate for **. → However, since the number of value candidates $ m $ in each round is large, I could not make the calculation in time, and I tried to reduce $ m $, but I could not consider it well.
In fact, if you develop Policy 2, you can get closer to the correct solution. Policy 2 above is a transition of ** state, so you can think about DP **, and prepare an array to save the state of $ DP $ as shown below.
$ DP [i] = $ (a set of $ t $ such that $ x = t $ before the $ i $ th round and the game continues from there to $ x = 0 $)
Considering the transition of DP [i] under this, it is as follows.
(1) When $ S_i = 0 $ ** The number 0 person wants to think of as many $ x $ candidates as possible **, so all he has to do is list all possible $ x $ candidates at the time of that round $ i $. Therefore, the transition of $ DP $ is as follows.
(2) When $ S_i = 1 $ ** The number 1 person wants to make $ x $ that is not included in the possible $ x $ candidates ($ DP [i + 1] $) at the time of the next round $ i + 1 $ ** When you think about it, it's easy to distinguish between cases. Now, considering $ x (\ in DP [i]) $ which is $ x \ notin DP [i + 1] $, the person with number 1 in round $ i $ does nothing and the final $ Since x $ can be non-zero, it needs to be $ x \ in DP [i + 1] $. Also, there is a possibility that $ x \ in DP [i + 1] $ is also $ x \ oplus A_i \ notin DP [i + 1] $, so the transition of $ DP $ at this time is as follows. ..
\begin{cases}
DP[i]=DP[i+1] \ \ \ \ ( ^∀ x\in DP[i+1])(x \oplus A_i \in DP[i+1])\\
DP[i]=0 \ \ \ \ (^∃ x \in DP[i+1])(x \oplus A_i \notin DP[i+1])\\
\end{cases}
<Policy 3> is a clarification of my <Policy 2> and I haven't been able to reduce the amount of calculation yet, but I will consider reducing the state from here. Consider that we represent $ DP [i] $ without preserving all the elements of the set of ** $ DP [i] $ **.
First of all, I think it is self-evident that ** expressed in mathematical formulas ** and $ DP [i] $ can be written as follows.
In the above expression, $ a_ {i}, a_ {i + 1},…, a_n $ is a constant multiple, and $ A_ {i}, A_ {i + 1},…, A_n $ is divided by bit and $ Assuming that the direct product set of \ {0,1 \} $ is the source, $ A_ {i}, A_ {i + 1},…, A_n $ can be regarded as vectors, respectively.
Therefore, ** $ DP [i] $ can be thought of as a vector space ** that can be represented by a linear combination of the vectors $ A_ {i}, A_ {i + 1},…, A_n $ by XOR. Furthermore, since the MSB (most significant bit) is at most 59 from $ 1 \ leqq A_i \ leqq 10 ^ {18} <2 ^ {60} $, the dimension of this vector space is at most 60.
Therefore, ** a basis is sufficient to represent this vector space **, and at most 60 integers should be stored. Therefore, consider preserving the basis in the DP transition. Normally, you should consider the basis using the sweep method **, but the sweep method is not in time for the computational complexity.
In fact, it's not too difficult to find the basis using the XOR features. ** When there are bases in a vector space with an XOR as a linear combination, each base can be defined as an integer of different MSBs ** (if $ \ because $ MSB takes those XORs for the same base) One MSB can be made smaller). … (✳︎)
According to this, the transition of DP can be thought of as follows as $ DP [i] = $ (set of bases of vector space represented by $ A_i $ ~ $ A_n $). (It is easy to understand by comparing with <Policy 3>.)
(1) When $ S_i = 0 $ For any $ v (\ in DP [i]) $, if $ A_i $ is linearly independent, then $ DP [i] = DP [i + 1] \ cup \ {A_i \} $ For any $ v (\ in DP [i]) $, if $ A_i $ is linearly dependent, then $ DP [i] = DP [i + 1] $
(2) When $ S_i = 1 $ $ DP [i] = 0 $ if $ A_i $ is linearly independent for any $ v (\ in DP [i]) $ For any $ v (\ in DP [i]) $, if $ A_i $ is linearly dependent, then $ DP [i] = DP [i + 1] $
Also, to determine whether it is linearly independent or linearly dependent, it is easy to implement by using the property of (✳︎) to ** store the bases with different MSBs in $ DP [i] $ **. That is, it should be defined as $ DP [i] [j] = $ (MSB of the vector space represented by $ A_i $ ~ $ A_n $ is the basis of $ j $). To determine if $ A_i $ is linearly independent of those bases under this, replace $ A_i $ with $ A_i $ and the XOR of that base if the same MSB base as $ A_i $ exists. ** ($ \ because $ (✳︎)) is repeated, and if $ A_i = 0 $ in the end, $ A_i $ is linearly dependent and there is no basis where MSB is equal to "MSB of $ A_i $". In this case, $ A_i $ can be determined to be linearly independent.
By determining whether it is linearly independent or linearly dependent by the above operation, the DP transition between (1) and (2) can be expressed, and $ O (t \ times n \ times (\ log {A_ {) max}}) ^ 2) You can write a program with a computational complexity of $.
A.py
import numpy as np
#0-indexed,When the MSB is less than or equal to ma
def msb(x,ma=59):
for i in range(ma,-1,-1):
if (x>>i)&1:
return i
return len()
t=int(input())
for _ in range(t):
n=int(input())
a=list(map(int,input().split()))
s=input()
#Independent, msb no one is the same
#On the contrary, if they are different, they become independent.
msbs=[0 for i in range(60)]
for i in range(n-1,-1,-1):
now=a[i]
m=59
#When independent, f is True, when not independent, f is False
while True:
m=msb(now,m)
if msbs[m]==0:
f=True
break
now=msbs[m]^now
if now==0:
f=False
break
if s[i]=="0":
if f:
msbs[m]=now
else:
if f:
print(1)
break
else:
print(0)
I can't solve it this time because I'm not good enough and I spent a lot of time on problem A.
Recommended Posts