E 猜结论

题意

给一个特殊的二分图，要求你算出它生成树的个数，其中顶点数

思路

如果图的定点数小于 ，可以用矩阵树定理爆算，复杂度

但是，这个图很大，尝试猜结论...

首先，从小图开始猜，比如样例3的基尔霍夫矩阵：

[ 1, 0, 0,-1, 0, 0 ],
[ 0, 2, 0,-1,-1,-1 ],
[ 0, 0, 3,-1,-1,-1 ],
[-1,-1,-1, 3, 0, 0 ],
[ 0,-1,-1, 0, 2, 0 ],
[ 0, 0,-1, 0, 0, 3 ]

其阶余子式的值为 , 因此答案为

比如样例2的基尔霍夫矩阵：

[ 2, 0,-1,-1 ],
[ 0, 2,-1,-1 ],
[-1,-1, 2, 0 ],
[-1,-1, 0, 2 ]

其阶余子式的值为 , 因此答案为

不妨猜，对这个特殊的二分图，记其度数序列为，其答案为：