CF1264D2 Beautiful Bracket Sequence

我们枚举每两个字符的空档，统计一个空档左边有 \(l\) 个左括号，

右边有 \(r\) 个右括号，左边有 \(u\) 个问号，右边有 \(v\) 个问号。

则对于 \(p\) 的答案 \(ans_p\) 有：

\[ans_p=\sum\limits_{i=0}^{u}(l+i)\dbinom{u}{i}\dbinom{v}{l+i-r}
\]

解释：

对于每个左边的问号枚举有几个变成左括号，则左边有 \(l+i\) 个左括号，方案数为 \(C_{u}^{i}\) ，右边的问号显然有 \(l+i-r\) 个变成右括号，则方案数为 \(C_{v}^{l+i-r}\) 相乘后求和即可。

弱化版直接暴力加和即可。

对于加强版显然 \(n<=1e6\) 直接枚举会 \(TLE\) ，于是考虑化简。

\[ans_p=\sum\limits_{i=0}^{u}l\dbinom{u}{i}\dbinom{v}{l+i-r}+\sum\limits_{i=0}^{u}i\dbinom{u}{i}\dbinom{v}{l+i-r}
\]

\[ans_p=l\sum\limits_{i=0}^{u}\dbinom{u}{i}\dbinom{v}{v+r-l-i}+\sum\limits_{i=0}^{u}u\dbinom{u-1}{i-1}\dbinom{v}{v+r-l-i}
\]

利用范德蒙恒等式得：

\[ans_p=l\dbinom{u+v}{v-l+r}+u\dbinom{u+v-1}{r+v-l-1}
\]

于是将所有 \(ans\) 相加即可。

Code

#include<cstring>

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

namespace EMT{

	typedef long long ll;typedef double db;//(double)clock() / (double)CLOCKS_PER_SEC;

	#define pf printf

	#define F(i,a,b) for(register int i=a;i<=b;i++)

	#define D(i,a,b) for(register int i=a;i>=b;i--)

	inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}

	inline void file(){freopen("in.in","r",stdin);freopen("my.out","w",stdout);}

	inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a<b?a:b;}

	inline void pi(int x){pf("%d ",x);}inline void pn(){pf("\n");}

	const int mod=998244353,N=1e6+100;int n,a[N],b[N],c[N],ans,jc[N];char s[N];

	inline int ksm(int a,int b){

		int ans=1;

		while(b){

			if(b&1)ans=1ll*ans*a%mod;

			a=1ll*a*a%mod;

			b>>=1;

		}return ans;

	}

	inline int C(int n,int m){

		if(n<m||m<0)return 0;

		if(!m)return 1;

		return (1ll*jc[n]*ksm(jc[m],mod-2)%mod)*ksm(jc[n-m],mod-2)%mod;

	}

	inline short main(){

		scanf("%s",s+1);n=strlen(s+1);

		F(i,1,n){

			a[i]=a[i-1],b[i]=b[i-1],c[i]=c[i-1];

			if(s[i]=='(')a[i]++;

			if(s[i]==')')b[i]++;

			if(s[i]=='?')c[i]++;

		}jc[0]=1;

		F(i,1,n)jc[i]=1ll*jc[i-1]*i%mod;

		F(i,1,n-1){

			int l=a[i],r=b[n]-b[i],u=c[i],v=c[n]-c[i];

			(ans+=(1ll*l*C(u+v,v-l+r)%mod+1ll*u*C(u+v-1,r+v-l-1)%mod)%mod)%=mod;

		}pi(ans);

		return 0;

	}

}

signed main(){return EMT::main();}

巴特西

CF1264D2 Beautiful Bracket Sequence

Code

最新文章

热门文章