解题报告——卡特兰数原理，容斥 count

woc，我今天一下午全都在盯这题的不到1K的代码……终于~~感性~~的搞懂了…… 另外这题好nb啊，卡特兰数总共就这么几个经典例子，一下子全串起来了…… 显然我们是要数笛卡尔树，并且它的右儿子可以和自己相等，左儿子必须严格小于自己。 然后上结论：只要任意一个点到根走的左儿子数不超过m那么就一定是合法的。 显然如果超过m了那值域肯定就不满足，并且这样的话我们一定能够对任意一棵满足这样的笛卡尔树构造一个可行的使用了1~m的所有数的序列，并且还很容易，所以这是对的。 其实咱们数的是二叉树。我们发现可以**把二叉树转化为括号序列**，显然二叉树和括号序列都是用卡特兰数计数的，你想想，它们分别的递推式的意义是啥，前者是枚举左儿子的大小，然后剩下右儿子是$Cat_{n-i-1}$，而后者则是枚举第一个完整的括号，把它外层剥掉划分成一个子问题$Cat_{i-1}$，再考虑剩下的$Cat_{n-i}$。所以，我们可以把一个子树的根看做包裹着左儿子括号序列的最外面一层括号，剩下的都是右儿子的，这样就完全的转化为括号序列了。 那么就很显然了，一个点到根走过的左儿子数就是前缀的未匹配左括号，我们现在归约为**求前缀左括号不超过m的括号序列数**。 看上去这个转化并没有什么卵用，然而我们考虑卡特兰数的另一个意义就是在坐标系上的路径计数，其实这有两个模型，一个是每次可以向上或向右走一步，不能越过$y=x$，求到$(n,n)$的方案数。另一个模型则是，每一步可以斜向上或斜向下一步，不能走到$y=0$以下，求到$(n,0)$的方案数。其实这两个在这题里都能用反正我用的是后者。 我们不妨先来考虑这么一个问题，卡特兰数为啥等于$\frac{C_{2n}^n}{n+1}$？这个就可以用这个坐标系模型解决，我们想，本来的总方案就是$C_{2n}^n$，但是这个可能走得太靠下，就是到达了$y=-1$直线，肯定得有个交点，我们考虑第一个交点，我们把这个交点右侧的直线**对称**一下，就变成了这样；  那么这个就等价于到$(n,-2)$并且往上走了$n-1$步的方案数（因为往上走和往下走的和是2n，差是-2），所以是$C_{2n}^{n-1}$，所以卡特兰数就是$C_{2n}^n-C_{2n}^{n-1}=\frac{C_{2n}^n}{n+1}$。 让我们回到这题，我们发现这题相当于是在上图上加了一条限制直线$y=m+1$，折线不能经过这，但是吧，咱可以容斥掉一条直线的，而两条直线的由于这个非法折线可能同时经过多次这两条直线，看上去很难处理。但是我们可以进一步用更加高级的容斥！我们可以模拟出这个折线**交替**的经过这两条直线的过程，每次我们都把终点关于某条直线做一次对称，容斥系数也取反，那么答案就是： $\sum_{i=1}^n(-1)^i(Path(x_i,y_i)+Path(x'_i,y'_i))$ 其中$(x_i,y_i)$是**最开始的时候经过上面那条直线**的交替了i次后的终点，$(x'_i,y'_i)$是**最开始的时候经过下面那条直线**的交替了i次后的终点，这两种交替过程并不一样所以要分开算。 于是代码真的只有0.8K…… ```cpp #include<iostream> #define ll long long #define p 998244353 using namespace std; ll jc[200001],jcny[200001]; inline ll mi(int a,int b){ ll ans=1,tmp=a;while(b){ if(b&1)ans=(ans*tmp)%p;tmp=(tmp*tmp)%p;b>>=1; }return(ans); } inline ll cnm(int n,ll m){ if(n<m||m<0)return(0);ll cjr=jc[n];cjr*=jcny[m];cjr%=p;cjr*=jcny[n-m];return(cjr%p); } int main(){ int n,m;cin>>n>>m;if(n<m){cout<<0<<endl;return(0);}jc[0]=1; for(register int i=1;i<=n*2;i++)jc[i]=(jc[i-1]*i)%p;jcny[n*2]=mi(jc[n*2],p-2); for(register int i=n*2-1;i>=0;i--)jcny[i]=(jcny[i+1]*(i+1))%p;ll ans=cnm(n*2,n); ll x=0,y=0;for(register int i=1;i<=n;i++){ x=2*(m+1)-x;y=-2-y;ans+=((i&1)?-1:1)*(cnm(n*2,(n*2+x)/2)+cnm(n*2,(n*2+y)/2));swap(x,y); }ans%=p;ans+=p;ans%=p;cout<<ans<<endl; return(0); } ```