这道题是考动态规划。下面就设计一下动态规划吧！~

1. 状态设计：dp(i, j)表示前i个括号插入若干个括号后，左括号比有括号多j个的插入方法数字。
2. 状态转移方程：dp(i,j)=dp(i-1,j-1)( $str_i$左括号)，dp(i,j)= $\Sigma_{k=0}^{j+1}dp(i-1, k)$（ $str_i$右括号）
3. 状态转移优化：当 $str_i$为右括号时，因 $dp(i,j-1)=\Sigma_{k=0}^{j}dp(i-1,k)$，由此dp(i,j)=dp(i-1,j+1)+dp(i,j-1)。利用前缀和将 $O(n)$的状态转移方程优化为 $O(1)$。
4. 初始状态： $dp(0,0)=1$

CAUTION：要增加 vis 数组用于表示 dp 数组每个位置取模前的实际值是否为 0，如果只判断 dp值可能会出现 dp值实际不为 0 但是因为取模恰好为 0 的情况（虽然因为这个模数的特殊性，这个情况出现的概率几乎为 0 ）

周末摸摸鱼~

下面直接开干！！！

代码

Python代码实现：

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2022/3/13 14:36
# @Author  : 府学路18号车神
# @Email   ：yurz_control@163.com
# @File    : demo.py

# 请在此输入您的代码
T = int(input())
for _ in range(T):
    a = list(map(int, input().split()))
    dp = []
    sum = 0
    ma = 0
    n = len(a)
    for i in range(1, n):
        dp.append(a[i])
        sum ^= a[i]
        ma = max(ma, a[i])

    if sum == 0:  # 每个不同位上的0和1个数分别为偶数
        print(0)
        continue

    x = 1
    while x < ma:
        x <<= 1

    while x > 0:
        one = 0
        zero = 0
        for i in dp:
            if i & x == 0:  # 关于x的第某位是否为0
                zero += 1
            else:
                one += 1
        if one % 2 == 1:  # 关于x的第某位1的个数为奇数
            if zero % 2 == 1 and one > 1:
                print(-1)
            else:
                print(1)
            break
        x >>= 1  # 关于x的第某位1的个数为偶数，则退位向下再次判断

由此，我们可以快速得出结果，验证完毕！明天最后一天，加油！！！

今天开刷第 十九 天，欢迎大家加入，一起变强，一起自律，一起上国赛！！！