T3
借鉴(chao xi)了神仙yijan的题解
题意:给一棵树,恰$n/2$个白点,$n/2$个黑点,每次将黑白点两两配对,求配对$n/2$次后恰有$i$对点为祖先-后代关系 的数量.(对998244353取模).
$n\le 5000$
解:恰$i$对不好求,因为树形dp时状态至少有三维,因此复杂度不会低于$\mathcal O(n^3)$
考虑求解”钦定(至少)$i$对点为祖先-后代 关系的数量”.记$dp(u,i)$表示以$u$为根的子树中钦定$i$对点的方案数.考虑转移:
- 枚举子树$v$中已配对的点的数量,做树形背包的转移
- 将当前点和某个后代配对
前者就是树形背包,因此时间复杂度为$\mathcal O(n^2)$(原理就是每对点仅在LCA处贡献一次),后者显然是$\mathcal O(n^2)$ .以此可以求出$f(i)$表示整棵树中钦定$i$对点,剩下的任意匹配:
$$
f(i)=dp(1,i)\times (n/2-i)!
$$
求出$f$后,即可求原答案:记$g(i)$表示恰有$i$对点为祖先-后代关系 的数量.因为有
$$
C^j_i=\frac{j!}{i!(j-i)!}\\
f(i)=\sum_{j\ge i}C_i^j g(j)
$$
二项式反演得:
$$
g(i)=\sum_{j\ge i}(-1)^{j-i} C^j_if(j)
$$
这个能预处理阶乘及其逆元算了. 时间复杂度$\mathcal O(n^2)$
