「雅礼集训 2017 Day11」PATH 题解

前置知识

在讲这题之前，先要知道一个概念——杨表。

杨表就是一个由一些长度递减的行组成的一个类似表的东西。

如图就是一个杨表的框架，每一行的长度都不超过上一行的长度。

一个合法的杨表是将一些数填进格子内，使得每一行，每一列的数都是递增的。

如图就是一个合法的杨表。

杨表有一个经典的应用，一个有 $S$ 个格子的杨表 $\lambda$，将 $1 \sim S$ 填进去的合法方案有多少种。

我们定义勾长为 $h(i,j)=a_i-j+b_j-i+1$，其中 $a_i,b_j$ 是第 $i$ 行，第 $j$ 列的长度，可以理解这个格子下面的格子数再加上右边的格子数加一。

将 $1 \sim S$ 填进杨表的合法方案，即勾长公式，为 $\frac{S!}{\prod_{(i,j)\in\lambda} h(i,j)}$。

证明我也不知道

思路

有了杨表，这题的思路就清晰了。由于 $a_i \ge a_{i+1}$，将 $a_1\sim a_n$ 看成一个 $n$ 行，第 $i$ 行有 $a_i$ 个元素的杨表，设 $S=\sum_{i=1}^{n}a_i$，将 $1 \sim S$ 填入杨表的过程相当于移动。

则合法方案数即为 $\frac{S!}{\prod_{(i,j)\in\lambda} h(i,j)}$，总期望即为：

$$\frac{\frac{S!}{\prod a_i!}}{{\frac{S!}{\prod_{(i,j)\in\lambda} h(i,j)}}}=\frac{\prod_{(i,j)\in\lambda} h(i,j)}{\prod a_i!}$$

如果暴力求每个格子的勾长，时间复杂度是 $O(n\times a_1)$ 的（$a_1$ 为 $a$ 中的最大数），无法通过。

考虑优化求勾长的过程。注意到，勾长可以表达为 $h(i,j)=(a_i-i)+(b_j-j)+1$，这样勾长就可以只通过行和列来表达了。

设 $m=a_1,X_i=a_i-i+n,Y_i=b_i-i+1+m$，则一个勾长 $h(i,j)=X_i+Y_j-n-m$（此处 $X_i,Y_i$ 加 $n,m$ 是为了方便NTT计算） 。 设 $f_x=\sum_{i=1}^n[X_i=x]，g_x=\sum_{i=1}^m[Y_i=x]$，则勾长 $d$ 在 $\lambda$ 中的出现次数即为 $\sum_{x+y=d+n+m}f_x\times g_y$。

注意到这个形式很NTT，考虑NTT，求出 $f,g$ 后进行卷积，设卷积后的结果 $h=f\times g$，勾长总和即为 $\prod_{d\ge 1}d^{h_{d+n+m}}$。

这样这题就做完了，时间复杂度为 $O(n \log n)$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1004535809;
ll n,a[500010],ff[500010],b[500010];
ll qpow(ll a,ll b){
	ll ans=1;
	for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
	return ans;
}
int r[8000010];
void NTT(ll a[],ll n,ll x){
	for(int i=0;i<n;i++)if(i<r[i])swap(a[i],a[r[i]]);
	for(int m=2;m<=n;m<<=1){
		ll g1=qpow(x,n/m);
		for(int i=0;i<n;i+=m){
			ll gk=1;
			for(int j=0;j<m/2;j++){
				ll x=a[i+j],y=a[i+j+m/2]*gk%mod;
				a[i+j]=(x+y)%mod;a[i+j+m/2]=(x-y+mod)%mod;
				gk=gk*g1%mod;
			}
		} 
	}
}
ll f[4000010],g[4000010];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	ff[0]=1;for(int i=1;i<=500000;i++)ff[i]=ff[i-1]*i%mod;
	ll ans=1;
	for(int i=1;i<=n;i++)ans=ans*ff[a[i]]%mod;
	for(int i=1,j=n;i<=a[1];i++){
		while(a[j]<i)j--;
		b[i]=j;
	}
	for(int i=1;i<=n;i++)f[a[i]-i+n]++;
	for(int i=1;i<=a[1];i++)g[b[i]-i+a[1]+1]++;
	ll m=n+a[1]+1,n=1;m<<=1;
	while(n<m)n<<=1;
	ll x=qpow(3,(mod-1)/n);
	for(int i=0;i<n;i++)r[i]=r[i>>1]/2+(i&1)*n/2;
	NTT(f,n,x);NTT(g,n,x);
	for(int i=0;i<n;i++){
		f[i]=f[i]*g[i]%mod;
	}
	NTT(f,n,qpow(x,mod-2));
	for(int i=0;i<n;i++){
		f[i]=f[i]*qpow(n,mod-2)%mod;
	}
	for(int i=1;i+m/2-1<n;i++)ans=ans*qpow(qpow(i,f[i+m/2-1]),mod-2)%mod;
	cout<<ans;
	return 0;
}

从路径到杨表：一道计数题的完整思路

---

第一步：题目在问什么？

想象你站在一个 $n$ 维空间的原点 $(0, 0, \dots, 0)$，要走到终点 $(a_1, a_2, \dots, a_n)$。

规则：

• 每一步，你选择某一维，让它的坐标 $+1$。
• 在行走的任何时刻，都必须满足 $x_1 \ge x_2 \ge \dots \ge x_n$。

问题：在所有可能的路径中随机选一条，它满足上述约束的概率是多少？

---

第二步：把路径想象成"堆方块"

这是最关键的思维转换。

把第 $i$ 维的坐标 $x_i$ 想象成第 $i$ 行堆了多少个方块：

x_1 = 4  →  ■ ■ ■ ■
x_2 = 3  →  ■ ■ ■
x_3 = 1  →  ■

• 起点 $(0,0,\dots,0)$：一行方块都没有，是一张白纸。
• 每走一步：在某一行的末尾添加一个方块。
• 约束 $x_1 \ge x_2 \ge \dots \ge x_n$：每一行的方块数不能少于下面一行。也就是说，你堆出来的图形必须始终是一个左对齐、上宽下窄（或等宽） 的阶梯形状。
• 终点 $(a_1, a_2, \dots, a_n)$：最终堆成了一个固定形状的"方块堆"。

📌 核心洞察：路径问题 = 堆方块问题。"每一步选哪一维" = "每一步往哪一行加方块"。

---

第三步：引入"杨表"——给方块编号

现在，我们引入一个记录工具：杨表。

什么是杨表？

杨表就是在方块堆里填数字。具体规则：

第 $t$ 步你往哪个格子加了方块，就在那个格子里写上数字 $t$。

• 数字代表时间（第几步）。
• 位置代表空间（哪一行哪一列）。

举个例子

$n=2$，终点 $(3, 2)$，总步数 $N=5$。

一条合法路径：

$$(0,0) \to (1,0) \to (2,0) \to (2,1) \to (3,1) \to (3,2)$$

逐步堆方块并编号：

步数	操作	方块堆变化
第1步	第1行加方块	第1行第1格，写 1
第2步		第1行第2格，写 2
第3步	第2行加方块	第2行第1格，写 3
第4步	第1行加方块	第1行第3格，写 4
第5步	第2行加方块	第2行第2格，写 5

最终杨表：

┌───┬───┬───┐
│ 1 │ 2 │ 4 │   ← 第1行（3个方块）
├───┼───┤
│ 3 │ 5 │       ← 第2行（2个方块）
└───┴───┘

形状 = $(3, 2)$ = 终点坐标。 填的数字 = 行走顺序。

---

第四步：杨表如何还原出一条路径？

反过来，给你一个杨表，你能唯一还原出路径：

按数字 1, 2, 3, … 从小到大看，数字在第几行，就表示那一步走了第几维。

上面那个杨表：

• 数字 1 在第 1 行 → 第1步走第1维
• 数字 2 在第 1 行 → 第2步走第1维
• 数字 3 在第 2 行 → 第3步走第2维
• 数字 4 在第 1 行 → 第4步走第1维
• 数字 5 在第 2 行 → 第5步走第2维

还原出的路径：$(0,0) \to (1,0) \to (2,0) \to (2,1) \to (3,1) \to (3,2)$ ✓

📌 结论：路径和杨表是一一对应的。知道路径就能画出杨表，知道杨表就能还原路径，不重不漏。

---

第五步：为什么"合法路径"恰好对应"标准杨表"？

我们填出来的杨表有一个重要性质：

行递增（同一行从左到右数字变大）

这是显然的：第 $i$ 行的方块只能从左到右依次添加，不可能先加右边再加左边。所以同一行的数字一定越来越大。

列递增（同一列从上到下数字变大）

这是约束条件的体现！

考虑第 $j$ 列：

• 第 $i$ 行第 $j$ 列的方块，表示"第 $i$ 维第 $j$ 次被增加"。
• 第 $i+1$ 行第 $j$ 列的方块，表示"第 $i+1$ 维第 $j$ 次被增加"。

约束 $x_i \ge x_{i+1}$ 意味着：

第 $i+1$ 维要达到 $j$，第 $i$ 维必须先达到 $j$。

翻译成时间：

第 $i$ 行第 $j$ 列的数字（时间）一定小于第 $i+1$ 行第 $j$ 列的数字（时间）。

这就是列递增！

如果路径非法呢？

假设第一步就走了第2维（此时 $x_1=0, x_2=1$，违反约束）：

• 第2行第1格填 1
• 第1行第1格填 2（更晚才加）

┌───┐
│ 2 │   ← 第1行
├───┤
│ 1 │   ← 第2行
└───┘

列不递增（$2 > 1$）！这不是一个合法的标准杨表。

📌 核心等价关系：

• 路径合法 ⟺ 杨表列递增
• 合法路径数 = 标准杨表数

---

第六步：什么是"标准杨表"？

满足以下三个条件的杨表称为标准杨表：

1. 填入的数字是 $1, 2, \dots, N$（$N$ 为总格子数），每个恰好用一次。
2. 每一行从左到右严格递增。
3. 每一列从上到下严格递增。

我们的路径填数恰好产生标准杨表，且只有合法路径才能产生标准杨表。

---

第七步：如何计算标准杨表的个数？——钩长公式

这是组合数学中一个极其优美的公式。

钩长（Hook Length）

对于杨表中的每个格子 $(i, j)$，它的"钩子"是：

• 它自己
• 它右边同一行的所有格子
• 它下面同一列的所有格子

钩长 $h(i,j)$ = 钩子里的格子总数。

例子：形状 $(3,2)$ 的钩长

格子(1,1): 右2 + 下1 + 自己1 = 4
格子(1,2): 右1 + 下1 + 自己1 = 3
格子(1,3): 右0 + 下0 + 自己1 = 1
格子(2,1): 右1 + 下0 + 自己1 = 2
格子(2,2): 右0 + 下0 + 自己1 = 1

钩长图：

┌───┬───┬───┐
│ 4 │ 3 │ 1 │
├───┼───┤
│ 2 │ 1 │
└───┴───┘

钩长公式

形状为 $\lambda$ 的标准杨表个数：

$$f^\lambda = \frac{N!}{\prod_{\text{所有格子}} h(i,j)}$$

对于 $(3,2)$：$f = \frac{5!}{4 \times 3 \times 1 \times 2 \times 1} = \frac{120}{24} = 5$。

📌 合法路径数 = $f^\lambda$。

---

第八步：计算概率

• 合法路径数 = $f^\lambda = \dfrac{N!}{\prod h(i,j)}$
• 总路径数（无约束）= 从 $N$ 步中选 $a_1$ 步给第1维、$a_2$ 步给第2维…… = $\dfrac{N!}{a_1! \cdot a_2! \cdots a_n!}$

概率：

$$P = \frac{\text{合法}}{\text{总数}} = \frac{\dfrac{N!}{\prod h(i,j)}}{\dfrac{N!}{\prod a_i!}} = \frac{\prod_{i=1}^n a_i!}{\prod_{(i,j) \in \lambda} h(i,j)}$$

$N!$ 被约掉了！最终只需要算分子（阶乘之积）和分母（钩长之积）。

---

第九步：如何高效计算钩长之积？

直接枚举所有格子算钩长是 $O(N)$ 的（$N = \sum a_i$ 可能高达 $2.5 \times 10^{11}$），不可行。

钩长的代数分解

$$h(i,j) = (a_i - j) + (b_j - i) + 1 = \underbrace{(a_i - i)}_{u_i} + \underbrace{(b_j - j)}_{v_j} + 1$$

其中 $b_j$ 是第 $j$ 列的长度（共轭分拆）。

关键性质：自动过滤非法格子

对于任意一对 $(i,j)$：

• 若 $(i,j)$ 在杨图内：$u_i + v_j \ge 0$
• 若 $(i,j)$ 在杨图外：$u_i + v_j \le -2$
• 不存在 $u_i + v_j = -1$ 的情况

所以：$u_i + v_j \ge 0$ 当且仅当 $(i,j)$ 是合法格子。

用卷积统计

构造两个多项式：

• $F[x]$：记录 $u_i = a_i - i$ 取各值的频次
• $G[y]$：记录 $v_j = b_j - j$ 取各值的频次

做多项式乘法 $H = F * G$，则 $H[k]$ = 满足 $u_i + v_j = k$ 的配对数。

我们只取 $k \ge 0$ 的项，对应的钩长为 $k+1$，累乘即可。

用 NTT（快速数论变换） 可在 $O(n \log n)$ 时间内完成。

---

第十步：完整算法流程

1. 读入 n 和 a[1..n]
2. 计算共轭分拆 b[1..m]（每列的长度）
3. 构造数组 F 和 G：
   - F[a_i - i + n]++     （偏移 n 避免负数）
   - G[b_j - j + m]++     （偏移 m 避免负数）
4. 对 F 和 G 做 NTT 卷积，得到 H
5. 计算分母 D = ∏ (K - n - m + 1)^{H[K]}，其中 K ≥ n+m
6. 计算分子 Num = ∏ a_i!
7. 答案 = Num × D^{-1} (mod p)

时间复杂度：$O((n+m) \log(n+m))$，空间 $O(n+m)$。

---

最终总结（一张图）

合法路径
    ↕ （双射：数字=步数，行=维度，列=第几次）
标准杨表（行递增 + 列递增）
    ↕ （钩长公式）
N! / ∏钩长
    ↕ （除以总路径数）
概率 = ∏a_i! / ∏钩长
    ↕ （钩长分解 + 卷积）
NTT 快速计算

一句话：路径是动态的，杨表是静态的。把"每一步的选择"编码为杨表中的数字，把"合法性约束"编码为列递增，就把一个复杂的路径计数问题，变成了一个可以用公式和多项式乘法秒杀的代数问题。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e6+10,P=1004535809;
int f[N],g[N],s[N],fac[N];
int qpow(int a,int b){int ans=1;for(;b;b>>=1,a=a*a%P)if(b&1)ans=ans*a%P;return ans;}
void ntt(int s[],int n,int x)
{
	if(n==1)return;
	int s1[n/2],s2[n/2];
	for(int i=0;i<n/2;i++)s1[i]=s[i*2],s2[i]=s[i*2+1];
	ntt(s1,n/2,x*x%P);ntt(s2,n/2,x*x%P);
	for(int i=0,xi=1;i<n/2;i++,xi=xi*x%P)
	{
		s[i]=(s1[i]+s2[i]*xi)%P;
		s[i+n/2]=((s1[i]-s2[i]*xi)%P+P)%P;
	}
}
void merge(int s1[],int len1,int s2[],int len2,int s[])
{
	int D=1;while(D<len1+len2-1)D<<=1;
	int inv=qpow(D,P-2),x=qpow(3,(P-1)/D);
	ntt(s1,D,x);ntt(s2,D,x);
	for(int i=0;i<D;i++)s[i]=s1[i]*s2[i]%P;
	int inv1=qpow(x,P-2);
	ntt(s,D,inv1);
	for(int i=0;i<D;i++)s[i]=s[i]*inv%P;
}
int a[N],b[N],d[N];
signed main()
{
	int n,m;cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];m=max(m,a[i]);
		b[a[i]]=i;
	}
	if(!m){cout<<1<<'\n';return 0;}
	fac[0]=1;for(int i=1;i<=m;i++)fac[i]=fac[i-1]*i%P;
	for(int i=m;i>=1;i--)b[i]=max(b[i],b[i+1]);
	for(int i=1;i<=n;i++)f[a[i]-i+n]++;
	for(int i=1;i<=m;i++)g[b[i]-i+m]++;
	merge(f,n+m,g,n+m,s);
	int sum1=1;
	for(int i=1;i<=n+m-1;i++)sum1=sum1*qpow(i,s[i+n+m-1])%P;
	int sum2=1;
	for(int i=1;i<=n;i++)sum2=sum2*fac[a[i]]%P;
	cout<<sum2*qpow(sum1,P-2)%P<<'\n';
	return 0;
}