求每行每列恰有两个1的n*n 0-1矩阵的数目. 输出前缀和对998244353取模的结果. 这是雅礼模拟考试的一道题 (by Owaski).
首先, 单次 的DP很容易. 一行一行考虑, 每行放两个1, 记录当前多少列有一个1, 多少列没有1. 写个记忆化搜索. 常数很小.
设当前在第 行, 列有一个1. 可以对列数之和, 1的数目之和列方程, 每种列有多少个直接解出来......或者直接yy......这样就是单次 了.
题目求的是前缀和. 用上面的状态, 每次得重新算. 考虑直接以 为状态, 设 为答案.
把 看成第 行到第 列的二分图 (多重) 匹配, 则所求的是完美匹配的数量.
这个二分图由一个个分离的环组成, 并且每个环左部,右部包含的点数相同. 不妨枚举1号点所在的环的大小/2, 再枚举这个环中有哪些点, 剩余的点集便是一个子问题
其中 是左右部各有 个点的完全二分图的生成环 (这个词是我造的......类比生成树) 的数目. 不妨把环先看成有向的, 以左部的1号点为起点, 那么, 一个环对应 (n-1的某排列, n的某排列). 由于顺逆时针各算了一次, 所以
代入化简, 最终可以 解决整个问题.
OEIS上给出了这样一个神奇的递推式 (考试的时候有大爷感受了一下, 用高斯消元消出来了......)
感谢坐我右边的右边的大爷教我推这个式子. >_<
设 为左部 个点, 右部 个点, 每个点度数为2的二分图的数目, 为左 右 , 右部有且仅有两个点度数为1, 其余点度数为2的二分图的数目. 我们求的是 .
考虑 中左部的1号点和右部的哪两个点连边, 右部的1号点和左部的哪两个点连边, 发现下述一一对应关系:
再来建立 的递推关系. 右部中那两个度数为1的点有两种情况: - 它们和左部的同一个点相连. . 这是多对一的映射, 所以要乘上组合数. - 它们和左部的两个不同点相连. 把右部这两个点去掉, 左部出现两个度数为1的点. . 因为 中已经包含两个度数为1的点的位置的所有情况, 所以不用乘上其他东西. 注意这里是排列数.
化简可得
令 , 化简后便得到了OEIS上的有趣二阶递推式.
启发: 1. 我联想到了 [bzoj 1059] [ZJOI2007]矩阵游戏, 却没有从0-1矩阵和二分图匹配的对应关系中找到灵感...... 2. 抽象成熟悉的模型. 3. 计数问题中的递推关系, 关键是要抓住对应关系.