Problem:


Score : 400 points

Problem Statement

There are two persons, numbered 0 and 1, and a variable x whose initial value is 0.
The two persons now play a game.
The game is played in N rounds. The following should be done in the i-th round (1 \leq i \leq N):

Person S_i does one of the following:

Replace x with x \oplus A_i, where \oplus represents bitwise XOR.

Do nothing.

Person 0 aims to have x=0 at the end of the game, while Person 1 aims to have x \neq 0 at the end of the game.

Determine whether x becomes 0 at the end of the game when the two persons play optimally.

Solve T test cases for each input file.

Constraints

1 \leq T \leq 100

1 \leq N \leq 200

1 \leq A_i \leq 10^{18}

S is a string of length N consisting of 0 and 1.

All numbers in input are integers.

Input

Input is given from Standard Input in the following format.
The first line is as follows:

T

Then, T test cases follow.
Each test case is given in the following format:

N
A_1 A_2 \cdots A_N
S

Output

For each test case, print a line containing 0 if x becomes 0 at the end of the game, and 1 otherwise.

Sample Input 1

3
2
1 2
10
2
1 1
10
6
2 3 4 5 6 7
111000

Sample Output 1

1
0
0

In the first test case, if Person 1 replaces x with 0 \oplus 1=1, we surely have x \neq 0 at the end of the game, regardless of the choice of Person 0.

In the second test case, regardless of the choice of Person 1, Person 0 can make x=0 with a suitable choice.



Sample input:
3
2
1 2
10
2
1 1
10
6
2 3 4 5 6 7
111000


Sample output:
1
0
0

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def deepcopy(li): return [x[:] for x in li]

def gauss_jordan(A, extended=False):
    """ ガウス・ジョルダン法(連立方程式の解) """

    N, M = len(A), len(A[0])
    B = deepcopy(A)
    rank = 0
    res = []
    for col in range(M):
        if extended and col == M-1:
            break
        pivot = -1
        for row in range(rank, N):
            if B[row][col] != 0:
                pivot = row
                break
        if pivot == -1:
            continue
        B[rank], B[pivot] = B[pivot], B[rank]
        for row in range(N):
            if row != rank and B[row][col]:
                for i in range(M):
                    B[row][i] ^= B[rank][i]
        res.append(col)
        rank += 1
    for row in range(rank, N):
        if B[row][-1]:
            return (-1, [])
    return (rank, res)

for _ in range(INT()):
    N = INT()
    A = LIST()
    S = input()
    M = max(A).bit_length()

    mat = list2d(M, 1, 0)
    for i in range(N-1, -1, -1):
        if S[i] == '0':
            for k in range(M):
                mat[k].append(A[i]>>k & 1)
        else:
            cur = deepcopy(mat)
            for k in range(M):
                cur[k].append(A[i]>>k & 1)
            rank, res = gauss_jordan(cur, extended=True)
            if rank == -1:
                print(1)
                break
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
def main():
    t = int(input())
    for _ in range(t):
        nn, aa, s, r, mm = int(input()), list(map(int, input().split())), input(), 0, []
        for ii in range(nn-1, -1, -1):
            ai = aa[ii]
            mm += [[(ai >> jj) & 1 for jj in range(64)]]
            n, i, j = r+1, 0, 0
            while i < n and j < 64:
                if mm[i][j] == 1 and mm[n-1][j] == 0:
                    i += 1
                    j += 1
                    continue
                if mm[i][j] == 0:
                    if mm[n-1][j] != 0:
                        for l in range(j, 64):
                            mm[i][l] ^= mm[n-1][l]
                    else:
                        j += 1
                        continue
                M2 = mm[i]
                for k in range(i+1, n):
                    M3 = mm[k][j]
                    mm[k][j] = 0
                    for l in range(j+1, 64):
                        mm[k][l] ^= M3*M2[l]
                i += 1
                j += 1
    
            if s[ii] == "0":
                if i > r:
                    r += 1
                else:
                    mm.pop()
            else:
                mm.pop()
                if i > r:
                    print(1)
                    break
        else:
            print(0)


main()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
	# T: test case数
	T = int(input())

	# test caseの実行
	for _ in range(T):
		# N: round数
		N = int(input())
		# XORする数
		A = input().split()
		# 人0 or 1
		S = list(input())

		# dpテーブル宣言
		# DP[i] = {t|t in DP[i-1] かつ i=Nでx=0になる}
		# 最後のroundで0になるケースを考えるので
		dp = {0}
		# 後ろから考える
		for i in range(N-1, -1, -1):
			a = int(A[i])
			# プレーヤー0の場合
			if S[i] == '0':
				# 解説pdfより、DP[i] = DP[i+1] U {v^a|v in DP[i+1]}
				dp = dp | {v^a for v in dp}
			# プレーヤー1の場合
			elif a not in dp:
				# プレーヤー１の勝ち？
				dp = {}
				break
		# x_0=0 で始まり、dp[0]はx_N=0になる場合の直前のxの値なので、
		if 0 in dp:
			print('0')
		else:
			print('1')

resolve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    # rankを出力、modを使って実装
    def matrix_rank(a):
        n, m = len(a), len(a[0])
        M = [[j for j in i] for i in a]
        rank = min(n, m)
        i, j = 0, 0
        while i < n and j < m:
            if M[i][j] == 0:
                for k in range(i+1, n):
                    if M[k][j] != 0:
                        for l in range(j, m):
                            M[i][l] ^= M[k][l]
                        break
                else:
                    j += 1
                    continue
            M2 = M[i]
            for k in range(i+1, n):
                M3 = M[k][j]
                M[k][j] = 0
                for l in range(j+1, m):
                    M[k][l] ^= M3*M2[l]
            i += 1
            j += 1
        return i

    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        s = input()
        r = 0
        m = []
        m2 = []
        for i in range(n-1, -1, -1):
            ai = a[i]
            b = [[(ai >> j) & 1 for j in range(64)]]
            newr = matrix_rank(m+b)
            if s[i] == "0":
                if newr > r:
                    r += 1
                    m += b
                    m2 += [ai]
            else:
                if newr > r:
                    print(1)
                    break
        else:
            print(0)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    # rankを出力、modを使って実装
    def matrix_rank(a, mod=2):
        n, m = len(a), len(a[0])
        M = [[j for j in i] for i in a]
        rank = min(n, m)
        i, j = 0, 0
        while i < n and j < m:
            if M[i][j] == 0:
                for k in range(i+1, n):
                    if M[k][j] != 0:
                        for l in range(j, m):
                            M[i][l] = (M[i][l]+M[k][l]) % mod
                        break
                else:
                    j += 1
                    continue
            pinv = pow(M[i][j], mod-2, mod)
            for k in range(m):
                M[i][k] = M[i][k]*pinv % mod
            M2 = M[i]
            for k in range(i+1, n):
                M3 = M[k][j]
                M[k][j] = 0
                for l in range(j+1, m):
                    M[k][l] = (M[k][l]-M3*M2[l]) % mod
            i += 1
            j += 1
        return i

    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        s = input()
        r = 0
        m = []
        m2 = []
        for i in range(n-1, -1, -1):
            ai = a[i]
            b = [[(ai >> j) & 1 for j in range(64)]]
            newr = matrix_rank(m+b)
            if s[i] == "0":
                if newr > r:
                    r += 1
                    m += b
                    m2 += [ai]
            else:
                if newr > r:
                    print(1)
                    break
        else:
            print(0)


main()

Submission status: Time Limit Exceeded

Solution code:
from copy import copy,deepcopy

class Matrix_Error(Exception):
    pass

class Matrix():
    #入力
    def __init__(self,M=[]):
        self.ele=M
        R=len(M)
        if R!=0:
            C=len(M[1])
        else:
            C=0
        self.row=R
        self.col=C
        self.size=(R,C)

    #出力
    def __str__(self):
        T=""
        (r,c)=self.size
        for i in range(r):
            U="["
            for j in range(c):
                U+=str(self.ele[i][j])+" "
            T+=U[:-1]+"]\n"

        return "["+T[:-1]+"]"
    #+,-
    def __pos__(self):
        return self

    def __neg__(self):
        return self.__scale__(-1)
    
    #加法
    def __add__(A,B):
        if A.size!=B.size:
            raise Matrix_Error("2つの行列のサイズが異なります.({},{})".format(A.size,B.size))
        M=A.ele
        N=B.ele

        L=[]
        for i in range(A.row):
            E=[]
            for j in range(A.col):
                E.append(M[i][j]+N[i][j])

            L.append(E)
        return Matrix(L)

    #減法
    def __sub__(A,B):
        return A+(-B)

    #乗法
    def __mul__(A,B):
        if isinstance(B,Matrix):
            R=A.row
            C=B.col

            if A.col!=B.row:
                 raise Matrix_Error("左側の列と右側の行が一致しません.({},{})".format(A.size,B.size))
            G=A.col

            M=A.ele
            N=B.ele
            
            E=[]
            for i in range(R):
                F=[]
                for j in range(C):
                    S=0
                    for k in range(G):
                        S+=M[i][k]*N[k][j]
                    F.append(S)
                E.append(F)

            return Matrix(E)
        
        elif isinstance(B,int):
            return A.__scale__(B)

    def __rmul__(A,B):
        if isinstance(B,int):
            return A*B

    def Inverse(M):
        if M.row!=M.col:
            raise Matrix_Error("正方行列ではありません.")

        R=M.row
        I=[[1*(i==j) for j in range(R)] for i in range(R)]
        G=M.Column_Union(Matrix(I))
        G=G.Row_Reduce()
        
        A,B=[],[]
        for i in range(R):
            A.append(copy(G.ele[i][:R]))
            B.append(copy(G.ele[i][R:]))

        if A==I:
            return Matrix(B)
        else:
            raise Matrix_Error("正則ではありません.")
        
    #スカラー倍
    def __scale__(A,r):
        M=A.ele
        L=[[r*M[i][j] for j in range(A.col)] for i in range(A.row)]
        return Matrix(L)

    #累乗
    def __pow__(A,n):
        if A.row!=A.col:
            raise Matrix_Error("正方行列ではありません.")

        if n<0:
            return (A**(-n)).Inverse()
        
        R=Matrix([[1*(i==j) for j in range(A.row)] for i in range(A.row)])
        D=A

        while n>0:
            if n%2==1:
                R*=D
            D*=D
            n=n>>1
                
        return R        

    #等号
    def __eq__(A,B):
        if A.size!=B.size:
            return False

        for i in range(A.row):
            for j in range(A.col):
                if A.ele[i][j]!=B.ele[i][j]:
                    return False

        return True

    #不等号
    def __neq__(A,B):
        return not(A==B)

    #転置
    def Transpose(self):
        (R,C)=self.size
        E=[[0]*R for _ in range(C)]

        for i in range(C):
            for j in range(R):
                E[i][j]=(self.ele)[j][i]

        return Matrix(E)
    
    #行基本変形
    def Row_Reduce(M):
        (R,C)=M.size
        T=[]

        for i in range(R):
            U=[]
            for j in range(C):
                U.append(M.ele[i][j])
            T.append(U)

        I=0
        for J in range(C):
            if T[I][J]==0:
                for i in range(I+1,R):
                    if T[i][J]!=0:
                        T[i],T[I]=T[I],T[i]
                        break

            if T[I][J]!=0:
                u=T[I][J]
                for j in range(C):
                    T[I][j]/=u

                for i in range(R):
                    if i!=I:
                        v=T[i][J]
                        for j in range(C):
                            T[i][j]-=v*T[I][j]
                I+=1
                if I==R:
                    break
                
        return Matrix(T)
    
    #列基本変形
    def Column_Reduce(M):
        (R,C)=M.size

        T=[]
        for i in range(R):
            U=[]
            for j in range(C):
                U.append(M.ele[i][j])
            T.append(U)
        
        J=0
        for I in range(R):
            if T[I][J]==0:
                for j in range(J+1,C):
                    if T[I][j]!=0:
                        for k in range(R):
                            T[k][j],T[k][J]=T[k][J],T[k][j]
                        break

            if T[I][J]!=0:
                u=T[I][J]
                for i in range(R):
                    T[i][J]/=u

                for j in range(C):
                    if j!=J:
                        v=T[I][j]
                        for i in range(R):
                            T[i][j]-=v*T[i][J]
                J+=1
                if J==C:
                    break
                
        return Matrix(T)
    
    #行列の階数
    def Rank(M,ep=None):
        M=M.Row_Reduce()
        (R,C)=M.size
        T=M.ele
        
        S=0
        for i in range(R):
            f=False
            if ep==None:
                for j in range(C):
                    if T[i][j]!=0:
                        f=True
            else:
                for j in range(C):
                    if abs(T[i][j])>=ep:
                        f=True

            if f:
                S+=1
            else:
                break

        return S

    #行の結合
    def Row_Union(self,other):
        return Matrix(self.ele+other.ele)
    
    #列の結合
    def Column_Union(self,other):
        E=[]
        for i in range(self.row):
            E.append(self.ele[i]+other.ele[i])
            
        return Matrix(E)


class Modulo_Error(Exception):
    pass

class Modulo():
    def __init__(self,a,n):
        self.a=a%n
        self.n=n

    def __str__(self):
        return "{} (mod {})".format(self.a,self.n)

    #+,-
    def __pos__(self):
        return self

    def __neg__(self):
        return  Modulo(-self.a,self.n)

    #等号,不等号
    def __eq__(self,other):
        if isinstance(other,Modulo):
            return (self.a==other.a) and (self.n==other.n)
        elif isinstance(other,int):
            return (self-other).a==0

    def __neq__(self,other):
        return not(self==other)
    
    #加法
    def __add__(self,other):
        if isinstance(other,Modulo):
            if self.n!=other.n:
                raise Modulo_Error("異なる法同士の演算です.")
            return Modulo(self.a+other.a,self.n)
        elif isinstance(other,int):
            return Modulo(self.a+other,self.n)

    def __radd__(self,other):
        if isinstance(other,int):
            return Modulo(self.a+other,self.n)
        
    #減法
    def __sub__(self,other):
        return self+(-other)

    def __rsub__(self,other):
        if isinstance(other,int):
            return -self+other
        
    #乗法
    def __mul__(self,other):
        if isinstance(other,Modulo):
            if self.n!=other.n:
                raise Modulo_Error("異なる法同士の演算です.")
            return Modulo(self.a*other.a,self.n)
        elif isinstance(other,int):
            return Modulo(self.a*other,self.n)
        
    def __rmul__(self,other):
        if isinstance(other,int):
            return Modulo(self.a*other,self.n)
        
    #Modulo逆数
    def Modulo_Inverse(self):
        x0, y0, x1, y1 = 1, 0, 0, 1
        a,b=self.a,self.n
        while b != 0:
            q, a, b = a // b, b, a % b
            x0, x1 = x1, x0 - q * x1
            y0, y1 = y1, y0 - q * y1

        if a!=1:
            raise Modulo_Error("{}の逆数が存在しません".format(self))
        else:
            return Modulo(x0,self.n)
        
    #除法
    def __truediv__(self,other):
        return self*other.Modulo_Inverse()

    def __rtruediv__(self,other):
        return Modulo(other,self.n)*self.Modulo_Inverse()

    #累乗
    def __pow__(self,m):
        u=abs(m)

        r=Modulo(1,self.n)

        while u>0:
            if u%2==1:
                r*=self
            self*=self
            u=u>>1

        if m>=0:
            return r
        else:
            return r.Modulo_Inverse()

#------------------------------------
K=60
T=int(input())
for _ in range(T):
    N=int(input())
    A=list(map(int,input().split()))
    S=input()

    if S[-1]=="1":
        print(1)
        continue

    f=0
    B=Matrix([[0]]*K)
    L=0
    for k in range(N-1,-1,-1):
        if S[k]=="0":
            H=[]
            for x in range(K):
                H.append([Modulo(A[k]>>x,2)])
            B=B.Column_Union(Matrix(H))
            L+=1
        else:
            W=[]
            for x in range(K):
                W.append([Modulo(A[k]>>x,2)])
            
            V=(B.Column_Union(Matrix(W))).Row_Reduce()

            for i in range(K):
                g=0
                for j in range(1,L+1):
                    if V.ele[i][j]==1:
                        g=1

                if g==0:
                    if V.ele[i][-1]==1:
                        f=1                
        
    print(f)

Submission status: Time Limit Exceeded

Solution code:
def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        s = input()
        r = 0
        m = []
        m2 = []
        for i in range(n-1, -1, -1):
            ai = a[i]
            b = [[(ai >> j) & 1 for j in range(64)]]
            m = m+b
            M = [[jj for jj in ii] for ii in m]
            x = min(r+1, 64)
            newr = x
            for ii in range(x):
                if M[ii][ii] == 0:
                    for jj in range(ii+1, r+1):
                        if M[jj][ii]:
                            for kk in range(ii, 64):
                                M[ii][kk] ^= M[jj][kk]
                            break
                    else:
                        for jj in range(ii+1, 64):
                            if M[ii][jj] != 0:
                                for kk in range(ii, r+1):
                                    M[kk][ii] ^= M[kk][jj]
                                break
                        else:
                            newr -= 1
                M2 = M[ii]
                for jj in range(ii+1, r+1):
                    M3 = M[jj][ii]
                    M[jj][ii] = 0
                    for kk in range(ii+1, 64):
                        M[jj][kk] ^= M3*M2[kk]
            if s[i] == "0":
                if newr > r:
                    r += 1
                else:
                    m.pop()
            else:
                m.pop()
                if newr > r:
                    print(1)
                    break
        else:
            print(0)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    # rankを出力、modを使って実装
    def matrix_rank(a, mod=2):
        n, m = len(a), len(a[0])
        M = [[j for j in i] for i in a]
        rank = min(n, m)
        for i in range(min(n, m)):
            if M[i][i] == 0:
                for j in range(i+1, n):
                    if M[j][i] != 0:
                        for k in range(i, m):
                            M[i][k] ^= M[j][k]
                        break
                else:
                    for j in range(i+1, m):
                        if M[i][j] != 0:
                            for k in range(i, n):
                                M[k][i] ^= M[k][j]
                            break
                    else:
                        rank -= 1
            M2 = M[i]
            for j in range(i+1, n):
                M3 = M[j][i]
                M[j][i] = 0
                for k in range(i+1, m):
                    M[j][k] ^= M3*M2[k]
        return rank

    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        s = input()
        r = 0
        m = []
        m2 = []
        for i in range(n-1, -1, -1):
            ai = a[i]
            b = [[(ai >> j) & 1 for j in range(64)]]
            newr = matrix_rank(m+b)
            if s[i] == "0":
                if newr > r:
                    r += 1
                    m += b
                    m2 += [ai]
            else:
                if newr > r:
                    print(1)
                    break
        else:
            print(0)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    # rankを出力、modを使って実装
    def matrix_rank(a, mod=2):
        n, m = len(a), len(a[0])
        M = [[j for j in i] for i in a]
        rank = min(n, m)
        for i in range(min(n, m)):
            if M[i][i] == 0:
                for j in range(i+1, n):
                    if M[j][i] != 0:
                        for k in range(i, m):
                            M[i][k] = (M[i][k]+M[j][k]) % mod
                        break
                else:
                    for j in range(i+1, m):
                        if M[i][j] != 0:
                            for k in range(i, n):
                                M[k][i] = (M[k][i]+M[k][j]) % mod
                            break
                    else:
                        rank -= 1
            pinv = pow(M[i][i], mod-2, mod)
            for j in range(m):
                M[i][j] = M[i][j]*pinv % mod
            M2 = M[i]
            for j in range(i+1, n):
                M3 = M[j][i]
                M[j][i] = 0
                for k in range(i+1, m):
                    M[j][k] = (M[j][k]-M3*M2[k]) % mod
        return rank

    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        s = input()
        r = 0
        m = []
        m2 = []
        for i in range(n-1, -1, -1):
            ai = a[i]
            b = [[(ai >> j) & 1 for j in range(64)]]
            newr = matrix_rank(m+b)
            if s[i] == "0":
                if newr > r:
                    r += 1
                    m += b
                    m2 += [ai]
            else:
                if newr > r:
                    print(1)
                    break
        else:
            print(0)


main()

Submission status: Time Limit Exceeded

Solution code:
T=int(input())
import copy
for i in range(T) :
  N=int(input())
  A_list=list(map(int,input().split()))
  S=input()


  n_set_list=set([0])

  flag=False
  for j in range(1,N+1) :
    n_set_list1=copy.copy(n_set_list)
    value=A_list[-j]
    if S[-j]=='0' :

      b=list(n_set_list1)
      c=n_set_list1
      d=set(map(lambda x:x^value,b))
      
      c=c|d

      n_set_list=c
    else :
      if value not in  n_set_list1 :
        flag=True
        break
  if flag :
    print('1')
  else :
    print('0')

Submission status: Time Limit Exceeded

Solution code:
T=int(input())
import copy
for i in range(T) :
  N=int(input())
  A_list=list(map(int,input().split()))
  S=input()


  n_set_list=set([0])

  flag=False
  for j in range(1,N+1) :
    n_set_list1=copy.copy(n_set_list)
    value=A_list[-j]
    if S[-j]=='0' :

      b=list(n_set_list1)
      c=n_set_list1
      for item in b :
        c.add(item^value)
      n_set_list=c
    else :
      if value not in  n_set_list1 :
        flag=True
        break
  if flag :
    print('1')
  else :
    print('0')

Submission status: Time Limit Exceeded

Solution code:
T=int(input())
import copy
for i in range(T) :
  N=int(input())
  A_list=list(map(int,input().split()))
  S=input()
  

  n_set_list=set([0])

  flag=False
  for j in range(1,N+1) :
    n_set_list1=copy.copy(n_set_list)
    if S[-j]=='0' :

      b=list(n_set_list1)
      c=n_set_list1
      for item in b :
        c.add(item^A_list[-j])
      n_set_list=c
    else :
      if A_list[-j] not in  n_set_list1 :
        flag=True
        break
  if flag :
    print('1')
  else :
    print('0')

Submission status: Time Limit Exceeded

Solution code:
T=int(input())
import copy
for i in range(T) :
  N=int(input())
  A_list=list(map(int,input().split()))
  S=input()
  a=set()

  n_set_list=set([0])
  
  flag=False
  for j in range(1,N+1) :
    n_set_list1=copy.copy(n_set_list)
    if S[-j]=='0' :

      b=list(n_set_list1)
      c=n_set_list1
      for item in b :
        c.add(item^A_list[-j])
      n_set_list=c
    else :
      if A_list[-j] not in  n_set_list1 :
        flag=True
        break
  if flag :
    print('1')
  else :
    print('0')

Submission status: Time Limit Exceeded

Solution code:
T=int(input())
for i in range(T) :
  N=int(input())
  A_list=list(map(int,input().split()))
  S=input()
  a=set()

  n_set_list=set([0])
  import copy
  flag=False
  for j in range(1,N+1) :
    n_set_list1=copy.copy(n_set_list)
    if S[-j]=='0' :

      b=list(n_set_list1)
      c=n_set_list1
      for item in b :
        c.add(item^A_list[-j])
      n_set_list=c
    else :
      if A_list[-j] not in  n_set_list1 :
        flag=True
        break
  if flag :
    print('1')
  else :
    print('0')

Submission status: Time Limit Exceeded

Solution code:
T=int(input())
for i in range(T) :
  N=int(input())
  A_list=list(map(int,input().split()))
  S=input()
  a=set()
  n_set_list=[a for i in range(N+1)]
  n_set_list[-1]=set([0])
  flag=False
  for j in range(1,N+1) :
    if S[-j]=='0' :

      b=list(n_set_list[-j])
      c=n_set_list[-j]
      for item in b :
        c.add(item^A_list[-j])
      n_set_list[-j-1]=c
    else :
      if A_list[-j] in  n_set_list[-j] :
        n_set_list[-j-1]=n_set_list[-j]
      else :
        flag=True
        break
  if flag :
    print('1')
  else :
    print('0')

Submission status: Time Limit Exceeded

Solution code:
T = int(input())

for t in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    S = input()

    dp = [None] * (N + 1)
    dp[N] = set([0])
    for i in reversed(range(N)):
        a = A[i]
        if S[i] == "0":
            dp[i] = dp[i + 1].copy()
            for v in dp[i + 1]:
                dp[i].add(v ^ a)
        else:
            if a in dp[i + 1]:
                dp[i] = dp[i + 1]
            else:
                dp[i] = set()
    if 0 in dp[0]:
        print(0)
    else:
        print(1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    matrix=np.zeros((60,1))
    for i in range(n-1,-1,-1):
        ne=np.array([(a[i]>>j)&1 for j in range(60)])
        matrix=np.c_[matrix,ne]
        col=matrix.shape[1]
        ra=np.linalg.matrix_rank(matrix)
        if s[i]=="0":
            if col!=ra+1:
                matrix=np.delete(matrix,col-1,1)
        else:
            if col==ra+1:
                print(1)
                break
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    dp=[set() for i in range(n+1)]
    dp[n]={0}
    for i in range(n,0,-1):
        if s[i-1]=="0":
            for j in dp[i]:
                dp[i-1].add(j)
                dp[i-1].add(j^a[i-1])
        else:
            if a[i-1] in dp[i]:
                for j in dp[i]:
                    dp[i-1].add(j)
            else:
                print(1)
                break
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def solve(N, A, S):

    dp = [set() for _ in range(N + 1)]

    dp[-1].add(0)

    for i in range(N - 1, -1, -1):

        if S[i] == "0":
            dp[i] = dp[i + 1].copy()
            for v in dp[i + 1]:
                dp[i].add(v ^ A[i])
        else:
            if A[i] in dp[i + 1]:
                dp[i] = dp[i + 1].copy()
            else:
                dp[i] = set()

    return 0 in dp[0]


def main():
    for _ in range(gete(int)):
        N = gete(int)
        A = tuple(geta(int))
        S = gete()
        x = 0 if solve(N, A, S) else 1
        print(x)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from copy import deepcopy

def canMake(k, Nums):#Numsにある数でkを作れるか
    L = len(Nums)
    index = 0
    bit = []
    for i in reversed(range(60)):
        flag = 0
        for j in range(index, L):
            if Nums[j] & (1 << i) == (1 << i):
                flag = 1
                Nums[index], Nums[j] = Nums[j], Nums[index]
                bit.append(i)
                break
        if flag == 1:
            for j in range(L):
                if Nums[j] & (1 << i) == (1 << i) and index != j: Nums[j] ^= Nums[index]
        if flag == 1: index += 1
    ans = 0
    for i in range(60):
        if k & (1 << i) == (1 << i):
            if i in bit: ans ^= Nums[bit.index(i)]
    if ans == k: return True
    else: return False


def solve():
    input = sys.stdin.readline
    T = int(input())
    Ans = [0] * T
    for t in range(T):
        N = int(input())
        A = [int(a) for a in input().split()]
        S = input().strip("\n")
        used = []
        for i in reversed(range(N)):
            if S[i] == "0":
                used.append(A[i])
            else:
                compare = deepcopy(used)
                if not canMake(A[i], compare):
                    Ans[t] = 1
                    break
    
    print(*Ans, sep="\n")

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 逆から、人1が多かったらその時点で駄目、人0が人1の数を覆い尽くす必要がある
T = ir()

def solve():
    N = ir()
    A = lr()
    S = sr()
    dp = [set()] * (N+1)
    dp[N] = {0}
    for i in range(N-1, -1, -1):
        if S[i] == '0':
            dp[i] = dp[i+1].copy()
            for element in dp[i+1]:
                dp[i].add(element ^ A[i])
        elif S[i] == '1':
            if A[i] not in dp[i+1]:
                return 1
            else:
                dp[i] = dp[i+1].copy()
    return 0
    
for _ in range(T):
    print(solve())