自动搬运

查看原文

来自洛谷，原作者为

	7KByte **

搬运于2025-08-24 22:14:59，当前版本为作者最后更新于2022-02-11 15:04:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更好的体验尽在我的博客。

不用生成函数，目前比 rank2 快四倍。

首先这是一道不简单的数数思维题。

我们要统计对于所有排列的深度之和，直接做非常不方便。而数数题一般将条件化简，或找到等价的容易处理的条件。

这里求深度，等价于枚举一个点的祖先，它的祖先个数 $+1$ 就是它的深度。这样问题转化为求数对 $(u,v)$ 的贡献，即有多少排列使得 $v$ 是 $u$ 的祖先。

如果 $v$ 是 $u$ 的祖先，等价于 $a_v < a_u$，且 $u,v$ 之间没有小于 $a_v$ 的数。

如果不考虑其它限制条件，先求有多少个排列恰好有 $K$ 个逆序对。这是一个经典题目，直接定义状态 $f_{i,j}$ 表示长度为 $i$ 的逆序对数为 $j$ 的排列个数。枚举最后一位的 $i$ 种选择，分别是逆序对增加 $x\in[0,i - 1]$ 个，典型的背包模型，可以前缀和优化至 $\mathcal{O}(N^3)$。

现在有 $(u,v)$ 的限制条件，我们可以先固定 $u,v$ 之间的数，再固定 $u,v$，最后固定外面的数。不难发现除了位置 $v$，其余的数可以随便填，和上面的转移一模一样。对于位置 $v$，如果在 $u$ 后面，一定会产生 $v-u$ 个逆序对，否则一定不产生逆序对。

所以我们先跑 DP 求出 $f$。然后枚举 $v-u$，然后在背包中撤销 $(v-u)$，撤销后的 $f_{n - 1,K-\max(0,v-u)}$ 就是我们要求的贡献。

时间复杂度 $\mathcal{O}(N^3)$，代码没有一次乘法和取模，跑的飞快。

#define M 46600
#define N 305
int n, k, f[2][M], s[M], g[M], sz, ans[N];
#define ck(x) (x >= P ? x - P : x)
void undo(int x){
	memset(g, 0, sizeof(g));
	int cur = P - 1; g[0] = 1;
	rp(i, sz - x){
		if(i > x)ad(cur, g[i - x - 1]);
		su(cur, g[i] = ck(f[n & 1][i] + cur));
	}
}
int main() {
	read(n, k, P);
	f[0][0] = 1;
	rp(i, n){
		s[0] = f[i & 1][0] = 1, sz += i - 1;
		rp(j, sz){
			f[i & 1][j] = s[j] = ck(s[j - 1] + f[1 & (i - 1)][j]);
			if(j >= i)su(f[i & 1][j], s[j - i]);
		}
	}
	rp(i, n)ans[i] = f[n & 1][k];
	rp(t, n - 1){
		undo(t);
		rp(i, n - t){
			if(t <= k)ad(ans[i], g[k - t]);
			ad(ans[i + t], g[k]);
		}
	}
	rp(i, n)printf("%d ", ans[i]); el;
	return 0;
}