Ich habe mich dieses Mal entschieden, mich nicht von NoSub zurückzuziehen und am Wettbewerb teilzunehmen, aber als Ergebnis war es 0 vollständig. Diesmal habe ich jedoch nicht gesagt, dass die Überlegung unbefriedigend war, und es war eine Art Problem, das ich überhaupt nicht gemacht hatte, daher denke ich, dass es nicht geholfen werden kann. Außerdem wollte ich nicht nur ein A-Problem, sondern auch ein C-Problem lösen, aber ich konnte es nicht lösen, da die letzte Implementierung nicht abgeschlossen werden konnte. Es schien unmöglich, selbst wenn ich einen Tag lang darüber nachdachte, also werde ich es einmal überspringen, weil mir die Fähigkeiten fehlen. Das Update des Artikels ist in letzter Zeit langsam, daher werde ich mein Bestes geben, um das Tempo des Updates zu erhöhen.
Das Problem besteht darin, den Vorgang des Ersetzens (oder Nicht-Ersetzens) von $ x $ durch $ x \ oplus A_i $ durch $ i = 1 $ ~ $ n $ zu wiederholen und schließlich zu prüfen, ob es auf 0 gesetzt werden kann.
Das Gewinnen oder Verlieren wird in einem Kampfspiel für zwei Spieler entschieden. Überlegen Sie also, was mit dem Endzustand passieren wird (①). Es sollte auch beachtet werden, dass XOR ** jedes Bit unabhängig berechnen kann ** (②).
Zuerst habe ich festgestellt, dass es ein Sonderfall ist, dass $ x = 0 $ ist, weil alle Bits 0 sind. Daher dachte ich, dass es ziemlich schwierig sein würde, das Ziel von ** people 0 zu erreichen, und beschloss, diesen Fall zu untersuchen. Da sich jedoch jedes Bit unabhängig von der Prämisse (2) bewegt, dachte ich, dass es schwierig sein würde, es auffindbar zu finden, und lehnte diese Richtlinie ab.
Wenn $ x = 0 $ als der Zustand des Wertes von $ x $ angesehen wird, beträgt der Zustand von $ x $ in jeder Runde $ i $ höchstens $ 10 ^ {18} $, also $ m = 10 ^ {18} Ich dachte, wenn es $ wäre, könnte es mit $ O (mn) $ berechnet werden. In Kombination mit Annahme (1) betrachtet die Person mit der Nummer 0 einen Kandidaten für den Wert von $ x $ zum Zeitpunkt der Runde $ i $, der schließlich zu $ x = 0 $ und Nummer 1 wird Ich frage mich, ob ich einen Wert von $ x $ machen kann, der kein Kandidat für ** ist. → Da jedoch die Anzahl der Wertkandidaten $ m $ in jeder Runde groß ist, konnte ich die Berechnung nicht rechtzeitig durchführen und habe versucht, $ m $ zu reduzieren, aber ich konnte sie nicht gut berücksichtigen.
Wenn Sie Richtlinie 2 entwickeln, können Sie der richtigen Lösung näher kommen. Die obige Richtlinie 2 ist ein Übergang des Status **, sodass Sie an DP ** denken und ein Array vorbereiten können, um den Status $ DP $ wie unten gezeigt zu speichern.
$ DP [i] = $ (eine Menge von $ t $, so dass $ x = t $ vor der $ i $ -ten Runde und das Spiel von dort bis $ x = 0 $ fortgesetzt wird)
In Anbetracht des Übergangs von DP [i] unter diesem ist es wie folgt.
(1) Wenn $ S_i = 0 $ ** Die Person mit der Nummer 0 möchte an so viele $ x $ -Kandidaten wie möglich denken **. Alles, was sie tun muss, ist, alle möglichen $ x $ -Kandidaten zum Zeitpunkt dieser Runde $ i $ aufzulisten. Daher ist der Übergang von $ DP $ wie folgt.
(2) Wenn $ S_i = 1 $ ** Die Person Nummer 1 möchte $ x $ machen, die zum Zeitpunkt der nächsten Runde $ i + 1 $ nicht in den möglichen $ x $ Kandidaten ($ DP [i + 1] $) enthalten ist ** Wenn Sie darüber nachdenken, ist es einfach, zwischen Fällen zu unterscheiden. Wenn man nun $ x (\ in DP [i]) $ betrachtet, was $ x \ notin DP [i + 1] $ ist, tut die Person mit der Nummer 1 in Runde $ i $ nichts und das letzte $ Da x $ ungleich Null sein kann, muss es in DP [i + 1] $ $ x \ sein. Es besteht auch die Möglichkeit, dass $ x \ in DP [i + 1] $ auch $ x \ oplus A_i \ notin DP [i + 1] $ ist, sodass der Übergang von $ DP $ zu diesem Zeitpunkt wie folgt ist. ..
\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}
<Richtlinie 3> ist eine Klarstellung meiner <Richtlinie 2> und ich konnte den Rechenaufwand noch nicht reduzieren, aber ich werde in Betracht ziehen, den Status von hier aus zu reduzieren. Bedenken Sie, dass wir $ DP [i] $ darstellen, ohne alle Elemente des ** $ DP [i] $ -Satzes ** beizubehalten.
Zunächst halte ich es für selbstverständlich, dass **, ausgedrückt in mathematischen Formeln ** und $ DP [i] $, wie folgt geschrieben werden kann.
Im obigen Ausdruck ist $ a_ {i}, a_ {i + 1},…, a_n $ ein konstantes Vielfaches und $ A_ {i}, A_ {i + 1},…, A_n $ ist in Bits und $ unterteilt Unter der Annahme, dass die direkte Produktmenge von \ {0,1 \} $ verwendet wird, können $ A_ {i}, A_ {i + 1},…, A_n $ als Vektoren betrachtet werden.
Daher kann ** $ DP [i] $ als ein Vektorraum ** betrachtet werden, der durch eine lineare Kombination der Vektoren $ A_ {i}, A_ {i + 1},…, A_n $ durch XOR dargestellt werden kann. Da MSB (höchstwertiges Bit) höchstens 59 von $ 1 \ leqq A_i \ leqq 10 ^ {18} <2 ^ {60} $ ist, beträgt die Dimension dieses Vektorraums höchstens 60.
Daher ** reicht es aus, eine Basis zu haben, um diesen Vektorraum darzustellen **, und es reicht aus, höchstens 60 ganze Zahlen zu speichern. Erwägen Sie daher, die Basis im DP-Übergang beizubehalten. Normalerweise können Sie die Sweep-Methode verwenden, um über die Basis ** nachzudenken, aber die Sweep-Methode reicht hinsichtlich des Berechnungsbetrags nicht aus.
Tatsächlich ist es nicht allzu schwierig, die Basis mithilfe der XOR-Funktionen zu finden. ** Wenn Basen in einem Vektorraum mit XOR als linearer Verbindung existieren, kann jede Basis als Ganzzahl verschiedener MSBs definiert werden ** (wenn $ , weil $ MSB diese XORs für dieselbe Basis verwendet) Ein MSB kann verkleinert werden. … (✳︎)
Demnach kann der Übergang von DP wie folgt betrachtet werden als $ DP [i] = $ (eine Menge von Basen des Vektorraums, dargestellt durch $ A_i $ ~ $ A_n $). (Es ist leicht zu verstehen, wenn man es mit <Richtlinie 3> vergleicht.)
(1) Wenn $ S_i = 0 $ Wenn für $ v (\ in DP [i]) $ $ A_i $ linear unabhängig ist, ist $ DP [i] = DP [i + 1] \ cup \ {A_i \} $ Wenn für $ v (\ in DP [i]) $ $ A_i $ linear abhängig ist, ist $ DP [i] = DP [i + 1] $
(2) Wenn $ S_i = 1 $ $ DP [i] = 0 $, wenn $ A_i $ für $ v (\ in DP [i]) $ linear unabhängig ist Wenn für $ v (\ in DP [i]) $ $ A_i $ linear abhängig ist, ist $ DP [i] = DP [i + 1] $
Um zu bestimmen, ob es linear unabhängig oder linear abhängig ist, ist es einfach zu implementieren, indem die Eigenschaft von (✳︎) verwendet wird, um ** Basen mit verschiedenen MSBs in $ DP [i] $ ** zu speichern. Das heißt, es sollte definiert werden als $ DP [i] [j] = $ (MSB des durch $ A_i $ ~ $ A_n $ dargestellten Vektorraums ist die Basis von $ j $). Um festzustellen, ob $ A_i $ linear unabhängig von diesen Basen ist, ersetzen Sie $ A_i $ durch $ A_i $ und das XOR dieser Basis, wenn dieselbe MSB-Basis wie $ A_i $ vorhanden ist. ** ($ \ weil $ (✳︎)) wiederholt wird und wenn $ A_i = 0 $ am Ende ist, ist $ A_i $ linear abhängig und es gibt keine Basis, in der MSB gleich "MSB von $ A_i $" ist. In diesem Fall kann $ A_i $ als linear unabhängig bestimmt werden.
Durch Bestimmen, ob es durch die obige Operation linear unabhängig oder linear abhängig ist, kann der Übergang von DP in (1) und (2) ausgedrückt werden und $ O (t \ times n \ times (\ log {A_ {) max}}) ^ 2) Sie können ein Programm mit einem Berechnungsbetrag von $ schreiben.
A.py
import numpy as np
#0-indexed,Wenn MSB kleiner oder gleich ma ist
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()
#Unabhängig, msb niemand ist der gleiche
#Im Gegenteil, wenn sie unterschiedlich sind, werden sie unabhängig.
msbs=[0 for i in range(60)]
for i in range(n-1,-1,-1):
now=a[i]
m=59
#Wenn unabhängig, ist f wahr, wenn nicht unabhängig, ist f falsch
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)
Ich kann es diesmal nicht lösen, weil ich nicht gut genug bin und viel Zeit mit Problem A verbracht habe.
Recommended Posts