Problem
Description
给定一棵 个点的树。
对于一个图,定义其权值为其邻接矩阵的秩。
现选择一个边集 并将其删去,求所有 种删边方案的权值之和。
答案对 取模。
Constraints
Link
Solution
Analysis
由基础线代知识可知一个 square matrix 是满秩的当且仅当 :
故一个图的邻接矩阵是满秩的当且仅当 。
考虑将这个排列分解成若干个互不相交的循环,则对于每个循环 ,原图中都必定存在环 。
注意到森林中只存在长度为 的环(即一条边),故一片森林的邻接矩阵是满秩的当且仅当 。稍加思考可以发现这个条件相当于这片森林存在完美匹配。
由基础线代知识可知一个 square matrix 的秩等于其非零主子式的最大阶数,故森林 的权值等于其有完美匹配的最大子图的大小,亦即其最大匹配大小的两倍。
定根,设 表示仅考虑以点 为根的子树时点 不在最大匹配中的概率,有转移方程:
树形 DP 即可。
时间复杂度 。
Code
1 |
|