QOJ 4824 Bracket-and-bar Sequences

考虑到这个实际上没有特别好的表示方法。
不如从 \(n\le 25\)，猜想合法的序列数量不多。

考虑对这个计数。
类似于合法括号序计数，考虑把串拆为 \(\texttt{(}\cdots\texttt{|}\cdots\texttt{)}\cdots\) 来考虑。
那么令 \(f_i\) 表示 \(i\) 对 \(\texttt{(|)}\) 组成的序列的数量。
有转移 \(f_i = \sum\limits_{j = 0}^{n - 1}\sum\limits_{k = 0}^{n - 1 - j} f_j f_k f_{n - 1 - j - k}\)。

跑出来能发现 \(f_{25} = 1031147983159782228\le 2\times 10^{18}\)，那就可以对于不同的序列给一个不同的编号了。

先考虑 encode。
考虑类似上面转移，拆成 \(\texttt{(}\cdots\texttt{|}\cdots\texttt{)}\cdots\)，令这 \(3\) 部分中间的 \(\texttt{(|)}\) 的数量分别为 \(c_1, c_2, c_3\)。
首先类似转移，对于 \(i < c_1\lor (i = c_1\land j < c2)\) 的情况，把 \(f_i f_j f_{n - 1 - i - j}\) 都加上，这样子就能确定对应的 \(c_1 = i, c_2 = j\) 了。
然后考虑递归构造，得到三部分的权值 \(v_1, v_2, v_3\)，因为还要区分出这 \(3\) 部分的权值，再加上 \(f_{c_3}(f_{c_2}v_1 + v_2) + v_3\) 即可。

对于 decode。
考虑按照上面求 \(f_n\) 的顺序枚举 \(i, j\)，如果满足此时 \(s < f_i f_j f_{n - 1 - i - j}\)，就能知道 \(c_1 = i, c_2 = j, c_3 = n - 1 - i - j\)。
然后再根据上面的操作就能推出 \(v_1, v_2, v_3\)，递归构造即可。
如果 \(s\ge f_i f_j f_{n - 1 - i - j}\)，那么就说明不是这对，\(s\) 减去这个值即可。

\(x \le 1031147983159782228\le 2\times 10^{18}\)，时间复杂度 \(\mathcal{O}(n^2)\)。

#include<bits/stdc++.h>
using ll = long long;
const int maxn = 28;
ll f[maxn];
namespace Encode {
   ll solve(int n, std::string s) {
      if (! n)
         return 0;
      int p1 = 0, p2 = 0;
      for (int i = 0, cnt = 0; ; i++) {
         cnt += s[i] == '(', cnt -= s[i] == ')';
         if (cnt == 1 && s[i] == '|') p1 = i;
         if (! cnt) {p2 = i; break;}
      }
      int c1 = (p1 - 1) / 3, c2 = (p2 - p1 - 1) / 3, c3 = (n * 3 - 1 - p2) / 3;
      ll val = 0;
      for (int i = 0; i < n; i++)
         for (int j = 0; i + j < n; j++) {
            if (i == c1 && j == c2)
               return (solve(c1, s.substr(1, c1 * 3)) * f[c2] + solve(c2, s.substr(p1 + 1, c2 * 3))) * f[c3] + solve(c3, s.substr(p2 + 1, c3 * 3))
                      + val;
            val += f[i] * f[j] * f[n - 1 - i - j];
         }
      return -1;
   }
   inline void Main() {
      int n; std::string s;
      std::cin >> n >> s;
      std::cout << solve(n, s) << '\n';
   }
   inline void main() {
      f[0] = 1;
      for (int i = 1; i <= 25; i++)
         for (int j = 0; j < i; j++)
            for (int k = 0; j + k < i; k++)
               f[i] += f[j] * f[k] * f[i - 1 - j - k];
      int Ti;
      for (std::cin >> Ti; Ti--; ) Main();
   }
}
namespace Decode {
   std::string solve(int n, ll s) {
      if (! n)
         return "";
      for (int i = 0; i < n; i++)
         for (int j = 0; i + j < n; j++) {
            if (s < f[i] * f[j] * f[n - 1 - i - j]) {
               ll s3 = s % f[n - 1 - i - j], s2 = (s / f[n - 1 - i - j]) % f[j], s1 = s / f[n - 1 - i - j] / f[j];
               return "(" + solve(i, s1) + "|" + solve(j, s2) + ")" + solve(n - 1 - i - j, s3);
            }
            s -= f[i] * f[j] * f[n - 1 - i - j];
         }
      return "-1";
   }
   inline void Main() {
      int n; ll s;
      std::cin >> n >> s;
      std::cout << solve(n, s) << '\n';
   }
   inline void main() {
      f[0] = 1;
      for (int i = 1; i <= 25; i++)
         for (int j = 0; j < i; j++)
            for (int k = 0; j + k < i; k++)
               f[i] += f[j] * f[k] * f[i - 1 - j - k];
      int Ti;
      for (std::cin >> Ti; Ti--; ) Main();
   }
}
int main() {
   std::ios::sync_with_stdio(false);
   std::cin.tie(0), std::cout.tie(0);
   std::string tp; std::cin >> tp;
   tp == "encode" ? Encode::main() : Decode::main();
   return 0;
}