題意

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;
  }
}