题面

请务必不要吐槽我的标签

传送门

思路

一个很重要的结论：原序列的一组同构的解等价于同一棵拥有$n$个节点的笛卡尔树

注意笛卡尔树的定义：父亲节点是区间最值，并且分割区间为左右部分

所以如果两个序列的笛卡尔树同构，那么他们的每一个区间最小值位置相同，也就是原题目中的同构条件了

一个很重要的结论：定义笛卡尔树节点的深度为根到这个节点的路径上向左走的次数，那么合法序列的笛卡尔树所有节点深度不超过$m$

首先，我们可以定义区间的父节点是所有最值中最靠左的，那么容易得到，节点的左儿子中的所有权值严格小于当前节点

这样，我们往左走的次数一旦超过了$m$就意味着有$m$以上个不同的数出现在序列中

反之，我们可以证明对于一个没有深度超过$m$的节点的笛卡尔树一定能构造出一组合法的，$m$个数都被用过的解

首先，找到笛卡尔树上的最深链（设其长度为$len$），并把最长链上的节点构造成为$n$到$n-len+1$

然后，不断寻找最深的没有赋值的点，并赋值成为当前没有出现过的数中最小的

最后，对于仍然没有赋值的点，从根开始，令他们等于父亲的权值-1（注意根节点一定被赋值了）

一个很重要的结论：笛卡尔树等价于一个括号序列

于是问题转化为：求合法的括号序列，使其任何一前缀中左括号减掉右括号都小于等于$m$，的数量

这个问题我们可以利用折线法方便的解决：

一个很重要的方法：折线法可以解决括号序列问题

我们令左括号为$(+1,0)$，右括号为$(0,+1)$

那么显然问题被转化成了只在在$y=x$和$y=x+m$两条直线中间运行，最后到达$(n,n)$的不同折线的数量

这个问题中，我们可以容斥：越过一次折线以后我们就把终点关于那条折线对称一下，并乘上一个(-1)的系数

具体详见代码

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cassert>

#define MOD 998244353

#define ll long long

using namespace std;

inline int read(){

	int re=0,flag=1;char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-') flag=-1;

		ch=getchar();

	}

	while(isdigit(ch)) re=(re<<1)+(re<<3)+ch-'0',ch=getchar();

	return re*flag;

}

inline int qpow(int a,int b){

	int re=1;

	while(b){

		if(b&1) re=1ll*re*a%MOD;

		a=1ll*a*a%MOD;b>>=1;

	}

	return re;

}

int n,m,ans=0,f[1000010],finv[1000010];

inline void init(){

	int i,len=1000000;

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

	for(i=2;i<=len;i++) f[i]=1ll*f[i-1]*i%MOD;

	finv[len]=qpow(f[len],MOD-2);

	for(i=len;i>2;i--) finv[i-1]=1ll*finv[i]*i%MOD;

}

inline int C(int x,int y){

//	cout<<"C "<<x<<' '<<y<<' '<<f[x]<<' '<<finv[y]<<' '<<finv[x-y]<<'\n';

	return 1ll*f[x]*finv[y]%MOD*finv[x-y]%MOD;

}

inline void flip(int &x,int &y,int b){//关于折线翻转

	int tx=x,ty=y;

	x=ty+b;

	y=tx-b;

}

int main(){

	n=read();m=read();

	if(n<m){puts("0");return 0;}

	init();

	ans=C(n<<1,n);

	int i,x1=0,x2=0,y1=0,y2=0,d1=1,d2=-m-1;

	for(i=-1;i;i=-i){

		flip(x1,y1,(i>0?d1:d2));//这是两个不同的翻转方向

		flip(x2,y2,(i>0?d2:d1));

		if((x1>n||y1>n)&&(x2>n||y2>n)) break;

		if(x1<=n&&x1>=-n) ans=((ans+i*C(n<<1,n-x1))%MOD+MOD)%MOD;

		if(x2<=n&&x2>=-n) ans=((ans+i*C(n<<1,n-x2))%MOD+MOD)%MOD;

	}

	cout<<ans<<'\n';

}

巴特西

[2018集训队作业][UOJ424] count [笛卡尔树+括号序列+折线法+组合数学]

题面

思路

Code

最新文章

热门文章