题意

U2FsdGVkX19zQ5B/rWD9mFO+T2gQsnjn7omW30cFQTSdsAPZHPeVhYQKa26wR1CK
HuafEBuiqUQ/1qIBu+8z0kKTelJ7BrKiafSKMG845mzLXYbCLh8ktdIvpEPtyYCa
VuLljLSGUIXPHNTEjUPaIBkBOr2pdwYUBad0rHa1Aq400nfVi7ohUl1zJqFn95Bd
okj4LmveTYT2IJjr+cTQxllJDWLj10G7/amHkMrcpSMN4fMdyHK0Va9dycLzKkZF
PezyOOnVt8PnqlB8QDspgyABgMVG/RYbCOy8lW873CmesN0kC3vQoGou+tG99Vpy
7aaLyTMBim6ufAUnKtF9FSQBbCBK6sLzBOM1fzdL1/OOTg2fcfl24kPkMQPtyWM3
wjYe57LS4EEMz6PDUb1/aeIGQY/vTrMmLXKs9rESynYSfTv4ZzhoFlDBPLB5u23Z
GK/zp1d2GpfVs5Svgt03EXEQodJ5veNPyaeJG7q+JymC0aTjiy6xV8xttDGzYVMg
8Nh7TGpwJ2HeS9z0ssAYHvXEIbGz0cK8Pn5hngps5vGcn8cY+9OAxTqfQ17b1+gP
QkC6NfOd67GXKMxsRtxmZY/jBQ5dwxSV9GgciExFq1X6SN38Pn5xEQuKZ3SJxPzj
14j+2SzOUDKKU1T+hQnHy8cB7Rncsuw+Ug5sVdE6CrHcLuC799bR7Hsl+6m/IyYk
d18WvV6j9swu+FXrD9Xd8IPqPDY9tQ2y9ykW54q0yBI=

解析

首先，如果只有 ()()，那就相当于普通的 nim，然而对于 (())，可以将其变成任意多个 ()，这不能套用不同 nim 的结论了。

接下来的过程感觉非常 constructive。

考虑用一个集合来表示某一个递减括号序列。

对于任意满足去掉最左边的左括号和最右边的右括号后仍然是递减括号序列的递减括号序列，我们称其为单位序列。所有连续 2^i 个相同单位序列组成的串可以构成一个集合 S。构造一个双射 f 将任意一个递减括号序列 A 映射到 S 的一个子集。具体来说算出 A 中每个单位序列的出现次数，然后将这个出现次数根据其二进制表示进行拆分，对应到 S 中的元素。举个例子，(())(())()()()()()，这个例子中 (()) 出现了 2 次，所以有 (())(()) 这个元素在 f(A) 中，同理，() 出现了 5=4+1 次，所以有 ()()()() 和 () 元素在 f(A) 中。

定义 rec 和为所有递减括号序列对应的集合的对称差，当前状态必败，当且仅当 rec 和为空集。证明方法和 nim 游戏的方法类似。

  1. 对于所有序列都为空的情况，此时 rec 和为空，且显然是必败状态。
  2. 对于 rec 和为空的情况，不存在一种移动方案使得 rec 和仍然为空。由于每次移动必然改变了一个序列，这个序列对应的集合也一定被改变了，rec 和就一定会跟着改变。
  3. 对于 rec 和不为空的情况，一定存在一种移动方式使得 rec 和为空。假设当前 rec 和为 R，找到 R 中字典序最大的元素 x，x 必定在某个序列中出现过，假设这个序列是 A，则将 A 操作成 f(A) 和 R 的对称差对应的序列。首先经过这个操作之后，新的 rec 和一定为 0；其次，需要证明新的 A 字典序比旧的 A 小，即这是一个合法的操作。对于 A 中大于 x 的元素，他们不受影响，而 x 被删去了，对应序列位置变成了更小的元素，因此新 A 的字典序一定比旧 A 小。

实现

实现的时候，并不太需要真的去做这个二进制拆分，统计每个单位序列出现次数后再异或，就相当于二进制拆分后求对称差了。

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>

int main()
{
  int n;
  std::cin >> n;

  std::map<std::string, int> diff;

  for (int i = 0; i < n; i++) {
    std::string s;
    std::cin >> s;

    std::map<std::string, int> set;

    int p = 0;
    std::string t;
    for (auto i : s) {
      t.push_back(i);
      if (i == '(') p++;
      else p--;
      if (p == 0) {
        set[t]++;
        t.clear();
      }
    }

    for (const auto &[s, c] : set) {
      diff[s] ^= c;
      if (diff[s] == 0) diff.erase(s);
    }

    std::cout << (int)(diff.size() != 0) << std::endl;
  }
}