NOI2018模拟赛(六)Problem B

题目描述

考虑\(n\times n\)的\(01\)矩阵,你需要找到满足每一行每一列都恰好有两个\(1\)的矩阵个数。

设对于\(n\)的答案是\(f_n\),你需要输出的是\(\sum\limits_{i=1}^{n}f_i\)。

其中\(n\leq 10^7\)

题解

首先想到的经典的二分图模型,把每一行每一列都当作一个点,建立二分图,每一个行点向每一个列点连边,那么题目就转化成求这个二分图中每一个点都恰好找到两个匹配的情况数。

然后考虑如何从 \(f_i\) 转移到 \(f_{i+1}\)。

设 \(f_i\) 为左右各有 \(i\) 个点,每个点的度数都恰好为 \(2\) 的二分图数量。

设 \(g_i\) 为左边有 \(i\) 个点,右边有 \(i+1\) 个点,左边点的度数都为 \(2\),右边存在两个点的度数为 \(1\) 的二分图的数量。

首先有一个显然的结论 \(f_i=g_{i-1}\)。

分类讨论 \(g_i\) 是如何得到的。

1.\(g_i\)右侧两个度为 \(1\) 的点与左侧同一点相连,\(C_i^1C_{i+1}^2f_{i-1}\)。

2.\(g_i\)右侧两个度为 \(1\) 的点与左侧不同点相连,\(A_i^2g_{i-1}\)。

所以有 \(f_i=g_{i-1}=C_{i-1}^1C_i^2f_{i-2}+A_i^2f_{i-1}\)。

化简得 \(f_i=i(i-1)f_{i-1}+\frac{i(i-1)^2}{2}f_{i-2}\)。

可以\(O(n)\)解决问题。


在《NOI2018模拟赛(六)Problem B》上留下第一个评论