题解：P16958 [SCCPC 2026] 括号序列

· · 题解

更好的阅读体验

模拟赛搬了这个，完全不会，不理解为什么那么多人过。

唉小朋友来打不断网的模拟赛就是这样的。

读入的字符串为 S，则我们将满足条件的括号串分为两类：是 S 的前缀的字符串，以及非 S 的前缀的字符串。

对于前者，直接枚举 S 的每个前缀，判断该前缀是否为合法括号串即可。

对于后者，我们枚举答案与 S 的 LCP 为 S[1: t-1]。那么我们考虑合法括号串的一个刻画：假设答案串的长度为 2l，现有一个二维平面，初始在 (0, 0)，遇到 ( 就往右移动一个单位，遇到 ) 就往上移动一个单位。如果一条 (0, 0) \to (l, l) 的格路没有穿过 y = x（即没有碰到 y = x + 1），则这条路径对应的括号串是合法的。

假设我们在 S[1: t-1] 已经有了 a 个 (，b 个 )。显然若 S 和我们所构造的括号串的 LCP 长度为 t-1，我们必须要求括号串的第 t 位严格小于 S 的第 t 位，因此括号串的第 t 位必须为 (，S 的该位置必须为 )。因此当走完前 t 步，我们目前位于 (a+1, b) 的位置。则这种情形下，我们进一步枚举答案串长 2l，则合法的括号串个数等价于 (a+1, b) \to (l, l) 且不碰到 y = x+1 的路径条数。由经典反射容斥结论，这个方案数等于 (a+1, b) \to (l, l) 的自由路数量 \displaystyle{2l - a - b - 1 \choose l - a - 1}，再减去 (a+1, b) \to (l-1, l+1) 的自由路数量 \displaystyle{2l - a - b - 1 \choose l - a - 2}。因此对于单个 t，答案就是

\sum_{l = 1}^{n / 2} {2l - a - b - 1 \choose l - a - 1} - \sum_{l = 1}^{n / 2}{2l - a - b - 1 \choose l - a - 2}

现考虑这个式子的前半部分：记 x = l - a - 1，则 2l - a - b - 1 = 2x + a - b +1。又因为 l \le n/2，因此 x \le n/2 - a - 1。有

\sum_{l = 1}^{n / 2} {2l - a - b - 1 \choose l - a - 1} = \sum_{x = 0}^{n/2 - a - 1} {2x + a - b + 1 \choose x}

同理我们可以整理原式的第二项：

\sum_{l = 1}^{n / 2}{2l - a - b - 1 \choose l - a - 2} = \sum_{x = 0}^{n/2 - a - 2} {2x + a - b + 3 \choose x}

现在记 \displaystyle{f(i, j) = \sum_{x = 0}^j {2x + i\choose x}}。那么单个 t 的答案可以记为

f\left(a - b + 1, \frac{n}{2} - a - 1\right) - f\left(a - b + 3, \frac{n}{2} - a - 2\right)

注意到对于相邻的 t，a, b 的变化都是 O(1) 的。因此考虑通过类似莫队的方式快速求出多个 f(i, j) 的值。

首先考虑当 j 移动的时候 f(i, j) 的变化。由定义可知，\displaystyle{f(i, j+1) = f(i, j) + {2(j+1) + i \choose j + 1}}；f(i, j) \to f(i, j-1) 的转移是类似的。

接下来考虑 i 移动时 f(i, j) 的变化。注意到，

\begin{align} f(i, j) + f(i+2, j) &= \sum_{x = 0}^j {2x + i \choose x} + \sum_{x = 0}^j {2x + i + 2 \choose x} \nonumber \\ &= \sum_{x = 0}^j \left[{2x + i \choose x} + {2x + i \choose x-1}\right] + {2j + i + 2 \choose j} \nonumber \\ &= \sum_{x = 0}^j {2x + i + 1 \choose x} + {i + 2j + 2 \choose j} \nonumber \\ &= f(i+1, j) + {i + 2j + 2 \choose j} \nonumber \end{align}

请注意，上式中当 x = 0 时，\displaystyle{{2x + i \choose x - 1} = 0}，因此 \displaystyle{{2x + i \choose x} + {2x + i \choose x - 1} = {2x + i + 1 \choose x} = 1} 仍然成立。

那么我们只需要同时维护 f(i, j) 和 f(i+1, j) 的值，就可以由此推出 f(i+2, j) 的值了。同理，当 i 减小的同时也可以类似地计算变化。

那么本题在 O(n) 的时间下得到解决。

#include<bits/stdc++.h>
#define endl '\n'
#define N 2000006
#define MOD 998244353
using namespace std;
inline void add(int &x,int y) {x+=y,x-=x>=MOD?MOD:0;}
inline void dec(int &x,int y) {x+=MOD-y,x-=x>=MOD?MOD:0;}
int n,fac[N],ifac[N];
char ch[N];
int qpow(int x,int y=MOD-2)
{
  int ret=1;
  for(;y;y>>=1,x=1ll*x*x%MOD)if(y&1)ret=1ll*ret*x%MOD;
  return ret;
}
inline int binom(int x,int y)
{
  if(x<0||y<0||x<y)return 0;
  return 1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;
}
struct F {
  int res1,res2,i,j;
  F():res1(1),res2(1),i(0),j(0) {}
  inline void add_j() {j++,add(res1,binom(i+2*j,j)),add(res2,binom(i+1+2*j,j));}
  inline void dec_j() {dec(res1,binom(i+2*j,j)),dec(res2,binom(i+1+2*j,j)),j--;}
  inline void add_i()
  {
    int res3=((res2+binom(i+2*j+2,j))%MOD-res1+MOD)%MOD;
    res1=res2,res2=res3,i++;
  }
  inline void dec_i()
  {
    int res0=((res1+binom(i+2*j+1,j))%MOD-res2+MOD)%MOD;
    res2=res1,res1=res0,i--;
  }
  int f(int x,int y)
  {
    if(y<0)return 0;
    while(i<x)add_i(); while(i>x)dec_i();
    while(j<y)add_j(); while(j>y)dec_j();
    return res1;
  }
} f;
void solve()
{
  scanf("%d%s",&n,ch+1);
  int a=0,b=0,ans=0;
  for(int i=1;i<=n;i++)
  {
    if(ch[i]==')')add(ans,f.f(a-b+1,n/2-a-1)),dec(ans,f.f(a-b+3,n/2-a-2));
    a+=ch[i]=='(',b+=ch[i]==')';
    if(a==b)add(ans,1);
  }
  printf("%d\n",ans);
}
main()
{
  fac[0]=1;
  for(int i=1;i<N;i++)fac[i]=1ll*i*fac[i-1]%MOD;
  ifac[N-1]=qpow(fac[N-1]);
  for(int i=N-2;~i;i--)ifac[i]=1ll*(i+1)*ifac[i+1]%MOD;
  int T; scanf("%d",&T);
  while(T--)solve();
  return 0;
}