UOJ#424. 【集训队作业2018】count
如果一个序列满足序列长度为\(n\)，序列中的每个数都是\(1\)到\(m\)内的整数，且所有\(1\)到\(m\)内的整数都在序列中出现过，则称这是一个挺好序列。
对于一个序列\(A\)，记\(fA(l,r)\)为\(A\)的第\(l\)个到第\(r\)个数中最大值的下标（如果有多个最大值，取下标最小的）。
两个序列\(A\)和\(B\)同构，当且仅当\(A\)和\(B\)长度相等，且对于任意\(i≤j\)，均有\(fA(i,j)=fB(i,j)\)。
给出\(n,m\)，求有多少种不同构的挺好序列。答案对\(998244353\)取模。
输入格式
一行两个正整数\(n,m\)。
输出格式
一行一个整数，表示有多少种不同构的挺好序列。
样例一
input
3 2
output
4
显然\(n<m\)时答案为\(0\)。
解决这种题的思路就是找一个“等价条件”来计数。关于区间最大值的问题，我们可以用笛卡尔树。
对于一个笛卡尔树的每个节点\(v\)，\(ls_v<v,rs_v\leq v\)。所以，如果一个笛卡尔树的最长左链，也就是根到某个点的路径上经过的左儿子数量（加上根）超过\(m\)的话，那么就是无解的，因为此时至少要分配\(m+1\)个不同的权值。满足条件的话就一定有解。
有一个非常厉害的\(O(nlogn)\)的生成函数做法可以参考这篇博客。
其实还有个\(O(n)\)的做法。
一棵多叉树唯一对应一棵二叉树，反过来也是唯一对应的。一棵\(n\)个二叉树对应一棵\(n+1\)的点的多叉树（要补一个根）。原来的二叉树最长左链\(\leq m\)，对应多叉树的最大深度\(\leq m\)（根深度为\(0\)）。
考虑用括号序来解决这个问题。一棵\(n+1\)个点的树的可以表示为\((X)\)，其中\(X\)表示一个括号序列，左右两个括号是根，所以我们先将其删除，于是对应了一个\(n\)对括号的括号序列。我们设\((\)为\(+1\)，\()\)为\(-1\)，那么树的最大深度就是最大的前缀和，所以任意位置的前缀和\(x\)要满足\(0\leq x\leq m\)。
我们将这个东西抽象到一个坐标系上。初始起点在\((0,0)\)，每次操作使横坐标\(+1\)，纵坐标可以\(+1\)或者\(-1\)。要求任意时刻这个点不能达到\(y=m+1\)和\(y=-1\)这两条直线，求最终走到\((2n,0)\)的方案数。
折线定理
如果没有任何限制，那么从\((0,0)\)走到\((n,m)\)的方案数是\(C_{n}^{\frac{n+m}{2}}\)，设这个东西为\(path(n,m)\)
如果只有一个限制，比如\(y=-1\)，那么我们可以用折线定理。将\((0,0)\)沿\(y=-1\)对称到\((0,-2)\)，每一条\((0,-2)\to (n,m)\)的路径都唯一对应了原问题的一个非法路径。考虑将第一次达到\(y=-1\)的路径沿着\(y=-1\)对折回来就可以理解了。所以答案为\(path(n,m)-path(n,m+2)\)。
如果有两条线，那么就要容斥了。设这条线分别为\(a,b\)。一个非法序列可以表示为类似于\(aaabbb...aaabbb\)的一个序列，表示经过这两条线的情况。于是我们枚举这个序列的一个子序列\(ababab...\)。然后算出一定包含这个子序列的非法序列数。以包含\(ab\)的序列为例，我们先将起点\(p\)沿\(a\)翻折得到\(p'\)，然后再将\(p'\)沿\(b\)翻折得到\(p''\)，然后算出\(p''\)到\((2n,0)\)的方案数\(path(2n,0-{p''}_y)\)。计算跟复杂的序列就多次翻折。容斥系数为\((-1)^k\)，\(k\)为\(a,b\)的个数和。我们可以发现，\(p\)经过一次翻折，\(p_y\)就会增大，当\(p_y>n\)时，\(path\)一定为\(0\)。
代码：
#include#define ll long long#define N 20000005using namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}const ll mod=998244353;int fac[N],ifac[N];ll ksm(ll t,ll x) { ll ans=1; for(;x;x>>=1,t=t*t%mod) if(x&1) ans=ans*t%mod; return ans;}int n,m;void pre(int n) { fac[0]=1; for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod; ifac[n]=ksm(fac[n],mod-2); for(int i=n-1;i>=0;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;}ll C(int n,int m) {return n