count
如果一个序列满足序列长度为(n)，序列中的每个数都是(1)到(m)内的整数，且所有(1)到(m)内的整数都在序列中出现过，则称这是一个挺好序列。
对于一个序列(A)，记(f_A(l, r))为(A)的第(l)个到第(r)个数中最大值的下标（如果有多个最大值，取下标最小的）。
两个序列(A)和(B)同构，当且仅当(A)和(B)长度相等，且对于任意(ile j)，均有(f_A(i,j)=f_B(i,j))。
给出(n,m)，求有多少种不同构的挺好序列。答案对(998244353)取模。
(n,mleq 100000)。
题意转化
根据笛卡尔树的性质直接转化，得到正常题意
计数有多少大小为(N)的二叉树，满足从根节点走到任意一个节点向左走的次数不超过(M~(M=m-1))。
(1 ≤ N ≤ 10^6)。
题解
首先有一个(O(NM))的暴力DP。考虑按照先序遍历的顺序遍历这颗二叉树；那么在每个点处要么向左走，要么跳到其某个祖先（包括自己）处然后往右走。
那么DP的时候只需要记录当前是先序遍历的第几个点，以及向左走了多少次。转移用前缀和可以优化到线性。
具体而言，用 (f(i,j)) 表示先序遍历第 (i) 个点，它的祖先中有 (j) 个是往左走的方案数。转移：
-
(f(i,j)leftarrow f(i+1,j+1)) 走到左儿子的方案数。
-
(f(i,j)leftarrow f(i+1,k leq j)) 走到某个祖先的右儿子的方案数。这个显然可以前缀和优化。
这样做实际上在统计合法的先序遍历的序列的方案数，而每个先序遍历的序列一一对应了一个二叉树。
CO int M=1e5+10;
int fac[2*M],ifac[M];
CO int N=2e3+10;
int f[N][N],g[N][N];
int main(){
int n=read<int>(),m=read<int>();
if(m>n){
puts("0");
return 0;
}
if(m>=n-1){
fac[0]=1;
for(int i=1;i<=2*n;++i) fac[i]=mul(fac[i-1],i);
ifac[n+1]=fpow(fac[n+1],mod-2);
for(int i=n;i>=0;--i) ifac[i]=mul(ifac[i+1],i+1);
int ans=mul(fac[2*n],mul(ifac[n],ifac[n+1]));
printf("%d
",ans-(m==n-1));
return 0;
}
--m;
fill(f[n],f[n]+m+1,1);
copy(f[n],f[n]+m+1,g[n]);
for(int j=1;j<=m;++j) g[n][j]=add(g[n][j-1],g[n][j]);
for(int i=n-1;i>=1;--i){
for(int j=0;j<=m;++j) f[i][j]=add(f[i+1][j+1],g[i+1][j]);
copy(f[i],f[i]+m+1,g[i]);
for(int j=1;j<=m;++j) g[i][j]=add(g[i][j-1],g[i][j]);
}
printf("%d
",f[1][0]);
return 0;
}
优化DP可以考虑组合意义，即计数有多少个长度为(N)的非负整数序列(A)，满足：
- (0 ≤ A_i ≤ M)
- (A_1 = 0)
- (∀2 ≤ i ≤ N, A_i ≤ A_{i−1} + 1)
特判掉(M = 0)的特殊情况，对于第三条限制，常见的变换手段是令(P_i = i − A_i)。
-
(i − M ≤ P_i ≤ i)
-
(P_1 = 1,~P_{N+1} = N + 1)
-
(P_i ≥ P_{i−1})
即从((1,1))走到((N + 1,N + 1))，每次只能往右走和往上走，把每个(x)处的最高点当作(P_x)的值，那么不能经过(y = x − (M + 2))和(y =x + 1)两条直线的方案数。因为把最高点当做 (P_x) 的值，所以可以经过 (y=x-(M+1)) 这条直线。
多次翻折法，时间复杂度 (O(N))。
CO int N=2e5+10;
int fac[N],ifac[N];
IN int C(int n,int m){
return mul(fac[n],mul(ifac[m],ifac[n-m]));
}
int main(){
int n=read<int>(),m=read<int>();
if(m>n){
puts("0");
return 0;
}
--m;
fac[0]=1;
for(int i=1;i<=2*n;++i) fac[i]=mul(fac[i-1],i);
ifac[2*n]=fpow(fac[2*n],mod-2);
for(int i=2*n-1;i>=0;--i) ifac[i]=mul(ifac[i+1],i+1);
int ans=0,X=n+1,Y=n+1;
for(int i=1;;++i){
swap(X,Y);
if(i&1) X-=1,Y+=1;
else X+=m+2,Y-=m+2;
if(X<1 or Y<1) break;
int sum=C(X-1+Y-1,X-1);
ans=add(ans,i&1?sum:mod-sum);
}
X=n+1,Y=n+1;
for(int i=1;;++i){
swap(X,Y);
if(i&1) X+=m+2,Y-=m+2;
else X-=1,Y+=1;
if(X<1 or Y<1) break;
int sum=C(X-1+Y-1,X-1);
ans=add(ans,i&1?sum:mod-sum);
}
X=n+1,Y=n+1;
ans=add(C(X-1+Y-1,X-1),mod-ans);
printf("%d
",ans);
return 0;
}