ZJOI2022 树

经典的数数题，实在是做不来。

题意：构造两棵有根树，第一棵树 $i$ 的父亲在 $[1, i - 1]$，第二棵树 $i$ 的父亲在 $[i + 1, n]$。问有多少种方案使得 $\forall i\in [1, n]$，第一棵树和第二棵树有且只有一个满足 $i$ 是叶子。$n\leq 500$，需要输出所有 $n\in [2, lim]$ 的答案对 $P$ 取模的结果，$lim, P$ 输入给定。

有且只有明显在提示容斥。

容易发现我们限制一个节点是叶子是容易的，直接记录前面都有多少非叶子即可转移，于是可以得到状态 $f(i, x, y)$ 表示处理到 $i$，$[1, i]$ 第一棵树有 $x$ 个非叶子，$[i, n]$ 有 $y$ 个非叶子。主要是限制非叶子比较麻烦。

考虑容斥，假设我们选定的 $i$ 在第一棵树中是叶子，那么他在第二棵树中出现必须是非叶子。但是注意，我们不好限制非叶子。于是考虑容斥，虽然他是非叶子，我们考虑强制选择一个集合，使得集合内部的变为叶子，剩余的就不再需要考虑非叶子的问题了。这样容斥只需要是叶子容斥时系数乘 -1 即可，并且两边的容斥可以一起写。

边界状态就是开始的时候 $f(1, 1, i) = i$，统计答案就是 $\sum f(i, x, 1) \times x$。理解了写起来很简单。

for (int i = 2; i <= n; ++ i)
	{
		int ans = 0;
		for (int x = 1; x <= n; ++ x) ans = (ans + (LL) f[(i - 1) & 1][x][1] * x) % Mod;
		printf("%d\n", ans);
		for (int x = 1; x <= n; ++ x)
			for (int y = 1; y <= n; ++ y) f[i & 1][x][y] = 0;
		for (int x = 1; x <= n; ++ x)
			for (int y = 1; y <= n; ++ y) {
				if (!f[(i - 1) & 1][x][y]) continue;
				adj(f[i & 1][x][y] -= (LL) f[(i - 1) & 1][x][y] * x % Mod * y % Mod * 2 % Mod),
				f[i & 1][x][y - 1] = (f[i & 1][x][y - 1] + (LL) f[(i - 1) & 1][x][y] * x % Mod * (y - 1)) % Mod;
				f[i & 1][x + 1][y] = (f[i & 1][x + 1][y] + (LL) f[(i - 1) & 1][x][y] * x % Mod * y) % Mod;
			}
	}