《浅谈格路计数相关问题》学习笔记

( ext{Dyck}) 路

格路

定义： 格点（整点）、平面格路（只经过格点的路径）、长度（所走步数）。

*路

定义： 从 ((0,0)) 到 ((n,m)) 的，只用上步 (U=(0,1)) 和水平步 (L=(1,0)) 的格路称作 ((n,m)) *路（free path） 。记 ((n,m)) *路的集合为 (mathcal{F}(n,m))，数量为 (F(n,m)=#mathcal{F}(n,m))。有 (F(n,m)={n+mchoose n})。

((n,m)- ext{Dyck}) 路的计数

定义： 对于一条 ((n,m)) *路，若其不经过对角线 (y=frac{m}{n}x) 下方，则称其为 ((n,m)- ext{Dyck}) 路。记 ((n,m)- ext{Dyck}) 路的集合为 (mathcal{D}(n,m))，数量为 (D(n,m)=#mathcal{D}(n,m))。

定义： 对于 (P,Qin mathcal{F(n,m)})，其中 (P=u_1u_2ldots u_{n+m},Q=v_1v_2ldots v_{n+m}(u_i,v_iin{U,L}))。若 (exists i,u_{i+1}u_{i+2}ldots u_{n+m}u_1u_2ldots u_i=v_1v_2ldots v_{n+m})，则称 (P,Q) 等价。记 (P) 的等价格路集合为 ([P])。

定义： 对于 (P=u_1u_2ldots u_{n+m},in mathcal{F}(n,m))，记 (P_k=u_{k+1}u_{k+2}ldots u_{n+m}u_1u_2ldots u_k)，那么 ([P]={P_k|1leq kleq n+m})。定义 (P) 的周期为最小的 (k) 使得 (P=P_k)，记作 (period(P))。有 (period(P)=#[P])。

引理： 当 (not m) 时，(forall Pin mathcal{F}(n,m),period(P)=n+m)。

引理： 当 (not m) 时，(forall Pin mathcal{F}(n,m),#([P]capmathcal{D}(n,m))=1)。

证明： 存在性：若 (P otinmathcal{D}(n,m))，找到一个在对角线下方且距离对角线最远的的 (v)，将 (P) 从 (v) 处断开分成两条子路 (P=L_1L_2)，那么 (L_2L_1in mathcal{D}(n,m))；唯一性：即证在对角线下方且距离对角线最远的点唯一。假设存在两个这样的点，设为 (v_1(x_1,y_1),v_2(x_2,y_2)(0<x_1<x_2<n,0<y_1<y_2<m))。那么 (v_1v_2) 与对角线平行，即 (frac{y_2-y_1}{x_2-x_1}=frac{m}{n})，与 (mot n) 矛盾。

定理： 当 (not m) 时，(D(n,m)=frac{1}{n+m}{n+mchoose n})。

((n,m)- ext{Dyck}) 路计数

定义： 对于一条 ((n,m)) *路中的连续的两步。若为 (UL)，则称之为峰（peak），两步之间的点称作峰点；若为 (LU)，则称之为谷（valley），两部之间的点称作谷点。

定理： 记恰好有 (k) 个峰的 ((n,m)) *路的集合为 (mathcal{F}(n,m;k))，数量为 (F(n,m;k)=#mathcal{F}(n,m;k))。有 (F(n,m;k)={nchoose k}{mchoose k})。

证明： (mathcal{F}(n,m;k)) 与合法峰点集合 ({(x_i,y_i)}_{i=1}^k(0leq x_1<x_2<ldots<x_k<n,0leq y_1<y_2<ldots<y_kleq m)) 形成双射。

定理： 记恰好有 (k) 个峰的，首步为 (U)，末步为 (L) 的 ((n,m)) *路的集合为 (mathcal{F}^{UL}(n,m;k))，数量为 (F^{UL}(n,m;k)=#mathcal{F}^{UL}(n,m;k))。有 (F^{UL}(n,m;k)={n-1choose k-1}{m-1choose k-1})。

证明： 第一个峰点的横坐标必须为 (0)，最后一个峰点的纵坐标必须为 (m)。

定理： 记恰好有 (k) 个峰的 ((n,m)- ext{Dyck}) 路的集合为 (mathcal{D}(n,m;k))，数量为 (D(n,m;k)=#mathcal{D}(n,m;k))。当 (not m) 时，有 (D(n,m;k)=frac{1}{k}{n-1choose k-1}{m-1choose k-1})。

证明： 考虑将一条 (mathcal{D}(n,m;k)) 中的格路从谷点处断开成 (k) 条子路，将 (k) 种子路的循环移位拼接与 (mathcal{F}^{UL}(n,m;k)) 中的格路建立双射。

(t- ext{Dyck}) 路计数

定义： 对于一条 ((n,m)) *路，若其不经过对角线 (y=tx(tin mathbb{Z}^+)) 下方，则称其为 (t- ext{Dyck}) 路。特别地，若 (m=tn)，则称之为 (n) 阶 (t- ext{Dyck}) 路。

定理： (D(n,tn;k)=frac{1}{k}{n-1choose k-1}{tnchoose k-1})。

证明： 通过在开头添加/删除一个 (U)，建立 (mathcal{D}(n,tn;k)) 与 (mathcal{D}(n,tn+1;k)) 的双射（这一定合法，因为当 (0leq xleq n) 时，(y=tx) 与 (y=frac{tn+1}{n}x) 之间没有整点）。而 (not tn+1)，所以 (D(n,tn;k)=D(n,tn+1;k)=RHS)。

定理： (D(n,tn)=frac{1}{tn+1}{tn+nchoose n})。

证明： 可以仿照上一定理证明，也可以对上一定理的式子求和。

定理： 当 (mgeq tn) 时，从 ((0,0)) 到 ((n,m)) 的，恰好有 (k) 个峰的 (t- ext{Dyck}) 路的个数为 (D_t(n,m;k)=frac{m-tn+1}{n}{nchoose k}{mchoose k-1})。

定理： 当 (mgeq tn) 时，从 ((0,0)) 到 ((n,m)) 的 (t- ext{Dyck}) 路的个数为 (D_t(n,m)=frac{m-tn+1}{m+1}{n+mchoose n}={n+mchoose n}-t{n+mchoose n-1})。

( ext{Dyck}) 路的另一种等价定义

(n) 阶 (t- ext{Dyck}) 路是在 (x) 轴上方以上步 (U_t=(1,t))，下步 (D=(1,-1))，从 ((0,0)) 到 (((t+1)n,0)) 的格路。记 (n) 阶 (t- ext{Dyck}) 路的集合为 ( ilde{mathcal{D}}_t(n))，数量为 ( ilde{D}_t(n)=# ilde{mathcal{D}}_t(n))。记恰有 (k) 个峰的 (n) 阶 (t- ext{Dyck}) 路的集合为 ( ilde{mathcal{D}}_t(n;k))，数量为 ( ilde{D}_t(n;k)=# ilde{mathcal{D}}_t(n;k))。

定理： ( ilde{mathcal{D}}_t(n)) 与 (mathcal{D}(n,tn)) 构成双射。

证明： 对于 (Pinmathcal{D}(n,tn))，将其倒序得到 (P')，然后把 (L) 替换为 (U_t)，(U) 替换为 (D) 即可得到 ( ilde{mathcal{D}}_t(n)) 中的格路。反向的映射同理。

不相交格路

若无特殊说明，以下的路对均无序。

(n) 阶不交 ( ext{Dyck}) 路计数

定义： 对于 (P,Qinmathcal{D}(n,n))，称 ((P,Q)) 为 (n) 阶 ( ext{Dyck}) 路对。若 (Q) 始终不穿过 (P)，则称 ((P,Q)) 为一个不交 ( ext{Dyck}) 路对，否则称为相交 ( ext{Dyck}) 路对。

定理： (n) 阶不交 ( ext{Dyck}) 路对数为

[left|egin{array}{c}C_n&C_{n+1}\C_{n+1}&C_{n+2}end{array} ight|=C_nC_{n+2}-C_{n+1}^2 ]

其中 (C_n=frac{1}{n+1}{2nchoose n})，为卡特兰数的第 (n) 项。

证明： 不妨假设 (P) 始终在 (Q) 的上方，构造映射 ((P,Q) ightarrow( ilde{P}, ilde{Q}))，其中 ( ilde{P}=UUPLL)，( ilde{Q}) 为将 (Q) 向 ((1,1)) 平移一格后得到的从 ((1,1)) 到 ((n+1,n+1)) 的 ( ext{Dyck}) 路。那么 ((P,Q)) 相交当且仅当 (( ilde{P}, ilde{Q})) 有交点。考虑用总的 (( ilde{P}, ilde{Q})) 对数（为 (C_nC_{n+2})）减去有交点的对数。后一部分可以从第一个交点处拆开，建立与两条 (n+1) 阶 ( ext{Dyck}) 路（后一条从 ((1,1)) 开始）的双射，方案数为 (C_{n+1}^2)。

定理： (k) 条 (n) 阶不交 ( ext{Dyck}) 路对数为

[det(C_{n+i+j})_{i,j=0}^{k-1}=left|egin{array}{c}C_n&C_{n+1}&ldots&C_{n+k-1}\C_{n+1}&C_{n+2}&ldots&C_{n+k-2}\vdots&vdots&ddots&vdots\C_{n+k-1}&C_{n+k-2}&ldots&C_{n+2k-2}end{array} ight| ]

证明： 经过平移转化为无交点后利用 LGV 引理计算。

不交*路对计数

定义： 对于 (P,Qinmathcal{F}(n,m))。若 (Q) 始终不穿过 (P)，则称 ((P,Q)) 为一个不交*路对。若除起点和终点外 (P) 与 (Q) 无公共点，则称 ((P,Q)) 为一个不接触*路对。

定理： 记所有从 ((0,0)) 到 ((n,m)) 的不接触*路队的集合为 (mathcal{F}_{nt}(n,m))，个数为 (F_{nt}(n,m)=#mathcal{F}_{nt}(n,m))。有 (F_{nt}(n,m)=frac{1}{n}{n+m-1choose n-1}{n+m-2choose n-1})。

证明： 利用 LGV 引理直接计算：

[F_{nt}(n,m)=left|egin{array}{c}F(n-1,m-1)&F(n-2,m)\F(n,m-2)&F(n-1,m-1)end{array} ight|\={n+m-2choose n-1}^2-{n+m-2choose n}{n+m-2choose n-2}=RHS ]

定理： 记所有从 ((0,0)) 到 ((n,m)) 的不相交*路队的集合为 (mathcal{F}_{nc}(n,m))，个数为 (F_{nc}(n,m)=#mathcal{F}_{nc}(n,m))。有 (F_{nc}(n,m)=frac{1}{n+1}{n+m+1choose n}{n+mchoose n})。

证明： 对于 ((P,Q)in mathcal{F}_{nc}(n,m))，不妨假设 (P) 始终在 (Q) 的上方，那么 ((UPL,LQU)in mathcal{F}_{nt}(n+1,m+1))，形成双射。

例题

[NOI2018] 冒泡排序

简要题意

给定一个 (n) 阶排列 (q)，求有多少个字典序严格大于 (q) 的 (n) 阶排列 (p)，满足用冒泡排序将 (p) 排好序的最少次数为 (frac{1}{2}sum_{i=1}^n|i-p_i|)。

题解

容易发现，合法的 (p) 等价于没有长度 (>2) 的下降子序列。若没有字典序限制，可以考虑 dp：记 (f_{i,x}) 为填到第 (i) 位，前缀最大值为 (x) 的合法方案数。那么 (f_{i,x}=[xgeq i]sum_{y=1}^{x}f_{i-1,y})，这是因为当 (i) 填的不是 (x) 时只能填未填入的最小数。由于前 (i) 位的前缀最大值一定不小于 (i)，所以答案为 (D(n,n))。加入字典序的限制之后，枚举 (p_i>q_i) 的最小 (i)（同时要保证 (q_{1ldots i-1}) 合法），答案为 (sum_{i=1}^{k-1}D_1(n-mx_i-1,n-i+1))，其中 (k) 为 (q) 的最小非法前缀长度（若 (q) 合法则为 (n+1)），(mx_i) 为 (q) 的前 (i) 位最大值。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#define P 998244353
#define N 600005

inline int fmo(int x){
	return x+((x>>31)&P);
}

int T;

int n;

int fac[N<<1],ifac[N<<1];
inline void init(int x){
	fac[0]=1;
	for(int i=1;i<=x;i++)
		fac[i]=1ll*fac[i-1]*i%P;
	ifac[1]=1;
	for(int i=2;i<=x;i++)
		ifac[i]=fmo(P-1ll*P/i*ifac[P%i]%P);
	ifac[0]=1;
	for(int i=1;i<=x;i++)
		ifac[i]=1ll*ifac[i-1]*ifac[i]%P;
}

inline int C(int x,int y){
	if(x<0||y<0||x<y)
		return 0;
	return 1ll*fac[x]*ifac[y]%P*ifac[x-y]%P;
}
inline int D1(int x,int y){
	if(x<0||y<0||x>y)
		return 0;
	return fmo(C(x+y,x)-C(x+y,x-1));
}

std::set<int> s;

int ans;

int main(){
	init(12e5);
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			s.insert(i);
		ans=0;
		bool flg=0;
		for(int i=1,mx=0;i<=n;i++){
			int a;
			scanf("%d",&a);
			if(flg)
				continue;
			mx=std::max(mx,a);
			ans=fmo(ans+D1(n-mx-1,n-i+1)-P);
			if(a<mx&&a!=*s.begin())
				flg=1;
			s.erase(a);
		}
		printf("%d
",ans);
	}
}