自动搬运

查看原文

来自洛谷，原作者为

	青葱 rush

搬运于2025-08-24 22:23:06，当前版本为作者最后更新于2020-07-25 18:21:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一个显然的结论是，右括号数目相同的括号序列出现的概率相同。

令$f_{i,j}$表示当前参数为$i$，$S$中右括号的数目是$j$。

则，

$$f_{i-1,j}=\frac{N-j+1}{N}\sum_{k=j-1}f_{i,k}\prod_{l=j}^{k}\frac{l}{N} $$

容易用前缀和优化得到全部的$f_{0,d}$。计算出了最终有$d$个括号序列的概率，除以个数，即可得到每一种有$d$个右括号的括号序列的概率。

接下来的问题转化为对长度给定的最长合法括号子序列计数。

考虑怎么求解一个括号序列的最长合法子序列长度，给出结论：

令$sum_i$表示令$'('$为$1$，$')'$为$-1$的前缀和，则有$ans=N-sum_n+2min\space sum_i$。

证明的话，考虑令$x$表示$sum_x$最小的位置，那么在此之前有$-sum_x$个右括号是不能匹配的，之后又有$(sum_n-sum_x)$个左括号不能匹配。减去不匹配的，即合法的。

问题即，为长度为$N$，共有给定个$\pm 1$，对前缀和不小于某一给定值的序列计数。考虑其组合意义，相当于初始在$(0,0)$，每次横坐标$+1$，纵坐标$\pm 1$，求出不经过某一条直线到达某一个点的方案数。折线法即可。

总复杂度$O(NK+N^2)$。

#include<bits/stdc++.h>
using namespace std;
template<typename T>inline T read(){
	T f=0,x=0;char c=getchar();
	while(!isdigit(c)) f=c=='-',c=getchar();
	while(isdigit(c)) x=x*10+c-48,c=getchar();
	return f?-x:x;
}
namespace run{
	const int N=5009,mod=998244353;
	inline int add(int x,int y){return x+y>=mod?x-mod+y:x+y;}
	inline int sub(int x,int y){return x>=y?x-y:x+mod-y;}
	inline int qpow(int x,int y){
		int ret=1;
		while(y){
			if(y&1) ret=1LL*x*ret%mod;
			x=1LL*x*x%mod,y>>=1;
		}
		return ret;
	}
	int fac[N],ifac[N];
	inline int C(int n,int m){
		if(n<0 || m<0 || n<m) return 0;
		return 1LL*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
	}inline int calc(int n,int d,int m){return sub(C(n,n-d-m),C(n,n-d-m+1));}

	int f[N][N],n,k,inv;
	int main(){
		n=read<int>(),k=read<int>(),inv=qpow(n,mod-2);
		fac[0]=ifac[0]=ifac[1]=1;
		for(int i=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%mod;
		ifac[n]=qpow(fac[n],mod-2);
		for(int i=n-1;i>=1;i--) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
		assert(1LL*fac[n-1]*ifac[n-1]%mod==1);

		f[0][0]=1;
		for(int i=1;i<=k;i++){
			int sum=f[i-1][n];
			for(int j=min(n,i);j;j--){
				sum=(1LL*sum*j%mod*inv+f[i-1][j-1])%mod;
				f[i][j]=1LL*inv*(n-j+1)%mod*sum%mod;
			}
		}
		int chk=0;
		for(int i=0;i<=n;i++) chk=add(chk,f[k][i]);
		assert(chk==1);

		for(int i=1;i<=n;i++) f[k][i]=1LL*f[k][i]*qpow(C(n,i),mod-2)%mod;
		int ans=0;
		for(int i=1;i<=n;i++)
			for(int j=2;j<=n && min(i,n-i)>=j/2;j+=2)
				ans=(1LL*f[k][i]*calc(n,i,(j-2*i)/2)%mod*j+ans)%mod;
		printf("%d\n",ans);
		return 0;
	}
}
int main(){
#ifdef my
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
#endif
	return run::main();
}