ToB企服应用市场:ToB评测及商务社交产业平台

标题: CF1264D1/2 Beautiful Bracket Sequence (easy/hard version) [打印本页]

作者: 立聪堂德州十三局店 时间: 2024-8-21 14:45
标题: CF1264D1/2 Beautiful Bracket Sequence (easy/hard version)
这篇题解相对于其它题解对小白要友好一些。
模拟赛题，赛时 sb 了，\(n^2\) 都不会。
思路：

考虑什么情况下深度最大，容易发现 (((...))) 是肯定不劣的。
那么考虑罗列中心点的位置，设左边有 \(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)\)。
需要提前预处理阶乘和阶乘逆元。
完整代码：

[code]#include#define Add(x,y) (x+y>=mod)?(x+y-mod)

x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#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=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'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)