讲解 CF1264D1/2 Beautiful Bracket Sequence (easy/hard version)。

考虑用组合数算方案数，考虑范德蒙德卷积与组合意义优化计算过程。

这篇题解相对于其它题解对小白要友好一些。

模拟赛题，赛时 sb 了，\(n^2\) 都不会。

思路：

考虑什么情况下深度最大，容易发现 <code>(((...))) 是肯定不劣的。

那么考虑枚举中心点的位置，设左边有 \(a\) 个左括号和 \(x\) 个问号，右边有 \(b\) 个右括号和 \(y\) 个问号，然后我们来枚举深度 \(i\)，求 \(i\) 的贡献次数。

要使得深度为 \(i\)，则要左边新添 \(i-a\) 个左括号，右边新添 \(i-b\) 个右括号，直接组合数计算贡献：

\[\sum_{i=\min(a,b)}^{\min(a+x,b+y)} \binom{x}{i-a} \binom{y}{i-b} i

\]

这样直接算是 \(O(N^2)\) 的，可以通过弱化版。

int main(){

init();

scanf("%s",s+1);

n=strlen(s+1);

For(i,1,n){

if(s[i]==')')

b++;

if(s[i]=='?')

y++;

}

For(i,1,n){

if(s[i]=='(')

a++;

if(s[i]=='?')

x++,y--;

if(s[i]==')')

b--;

l=min(a,b),r=min(a+x,b+y);

For(j,l,r)

ans=Add(ans,C(x,j-a)*C(y,j-b)%mod*j%mod);

}

write(ans);

return 0;

}

考虑拆式子为：

\[\Big(\sum_{i=0}^{n} \binom{x}{i-a} \binom{y}{i-b} (i-b) \Big)+ \Big(\sum_{i=0}^{n} \binom{x}{i-a} \binom{y}{i-b} b \Big)

\]

先看右边的式子，可以用范德蒙德卷积。

范德蒙德卷积基本形式：

\[\binom{n+m}{k} = \sum_{i=0}^k \binom{m}{i} \binom{n}{k-i}

\]

证明：

考虑组合意义，在 \(n+m\) 个物品中选 \(k\) 的方案数，是等价于在 \(n\) 个物品中选 \(i\) 个且在 \(m\) 个物品中选 \(k-i\) 个的总方案和的。

现在对于右边的式子：

\[b \sum_{i=0}^{n} \binom{x}{i-a} \binom{y}{i-b} = b \sum_{i=0}^{n} \binom{x}{x+a-i} \binom{y}{i-b}

\]

考虑组合意义后可化为：

\[b \binom{x+y}{x+a-b}

\]

现在看左边的式子：

\[\sum_{i=0}^{n} \binom{x}{i-a} \binom{y}{i-b} (i-b)

\]

注意到：

\[\begin{aligned} \binom{n}{m} m &= \frac{n!m}{m!(n-m)!} \\ &= \frac{n!}{(m-1)!(n-m)!} \\ &= \frac{(n-1)!}{(m-1)!(n-m)!} n \\ &= \binom{n-1}{m-1} n \end{aligned}

\]

那么左边式子可以化为：

\[\sum_{i=0}^{n} \binom{x}{i-a} \binom{y-1}{i-b-1} y = y \sum_{i=0}^{n} \binom{x}{x+a-i} \binom{y-1}{i-b-1}

\]

后面一串也可以考虑组合意义化简后得：

\[y \binom{x+y-1}{x+a-b-1}

\]

则对于 \(i\) 这个位置的总贡献为：

\[b \binom{x+y}{x+a-b} + y \binom{x+y-1}{x+a-b-1}

\]

现在时间复杂度优化为 \(O(N + \log P)\)。

需要提前预处理阶乘和阶乘逆元。

完整代码：

#include<bits/stdc++.h>

#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)

#define lowbit(x) x&(-x)

#define pi pair<ll,ll>

#define pii pair<ll,pair<ll,ll>>

#define iip pair<pair<ll,ll>,ll>

#define ppii pair<pair<ll,ll>,pair<ll,ll>>

#define fi first

#define se second

#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x

#define Full(a) memset(a,0,sizeof(a))

#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);

#define For(i,l,r) for(int i=l;i<=r;i++)

#define _For(i,l,r) for(int i=r;i>=l;i--)

using namespace std;

typedef double db;

typedef unsigned long long ull;

typedef long long ll;

bool Begin;

const ll N=1e6+10,mod=998244353;

inline ll read(){

ll x=0,f=1;

char c=getchar();

while(c<'0'||c>'9'){

if(c=='-')

f=-1;

c=getchar();

}

while(c>='0'&&c<='9'){

x=(x<<1)+(x<<3)+(c^48);

c=getchar();

}

return x*f;

}

inline void write(ll x){

if(x<0){

putchar('-');

x=-x;

}

if(x>9)

write(x/10);

putchar(x%10+'0');

}

ll ans;

ll n,l,r,a,b,x,y;

ll f[N],inv[N];

char s[N];

ll qpow(ll a,ll b){

ll ans=1;

while(b){

if(b&1ll)

ans=(ans*a)%mod;

a=(a*a)%mod;

b>>=1ll;

}

return ans;

}

void init(){

f[0]=f[1]=1;

For(i,2,n)

f[i]=(f[i-1]*i)%mod;

inv[n]=qpow(f[n],mod-2);

_For(i,0,n-1)

inv[i]=inv[i+1]*(i+1)%mod;

}

ll C(ll n,ll m){

if(m>n||m<0||n<0)

return 0;

if(!m||m==n)

return 1;

return f[n]*inv[m]%mod*inv[n-m]%mod;

}

bool End;

int main(){

scanf("%s",s+1);

n=strlen(s+1);

init();

For(i,1,n){

if(s[i]==')')

b++;

if(s[i]=='?')

y++;

}

For(i,1,n){

if(s[i]=='(')

a++;

if(s[i]=='?')

x++,y--;

if(s[i]==')')

b--;

ans=Add(ans,(b*C(x+y,x+a-b)%mod+y*C(x+y-1,x+a-b-1)%mod)%mod);

}

write(ans);

return 0;

}