LOJ 6160 二分图染色 （dp，组合数学）

LOJ 6160 二分图染色 （dp，组合数学）

题目描述

给定一个完全二分图，图的左右两边的顶点数目相同。我们要把图中的每条边染成红色、蓝色、或者绿色，并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。计算所有满足条件的染色的方案数，并对 109+7 10 9 + 7

输入格式

二分图单边的顶点数目 n n

输出格式

输出一个整数，即所求的答案。

样例输入

2

样例输出

35

思路

已知红色与蓝色的边存在限制，因此我们只考虑这两种颜色，完全二分图剩下的边置为绿色。

两边不共享端点的问题可以转化为棋盘模型，即在 n×nn×n 的棋盘上放红蓝棋子，每个格子至多放一次，同行同列的棋子不能同色，显然，对于每一种颜色我们有 Fn=∑ni=0Cin×Ain F n = ∑ i = 0 n C n i × A n i

考虑两种颜色同时存在，此时 Fn×Fn F n × F n 中包含这两种颜色同方格的情况，因此我们考虑容斥减掉这部分，最终结果为： ∑ni=0(−1)nCinAin(Fn−i)2 ∑ i = 0 n ( − 1 ) n C n i A n i ( F n − i ) 2

我们可以通过预处理最终在 O(1) O ( 1 ) 的时间内求出组合数与排列数，但是对于每一个 F F ，我们需要 O(n)O(n)

我们考虑 Fn F n 从前一个状态 Fn−1 F n − 1 的转移，即在格子的第 n n 行的 nn 个空中，我们可以染或者不染某一个方格，该方案数为 2n×Fn−1 2 n × F n − 1 ，但是第 n n 行的染色操作可能会与之前 n−1n−1 行中的某个方案冲突，横向 n−1 n − 1 个格子，纵向 n−1 n − 1 行，总方案数 (n−1)2×Fn−2 ( n − 1 ) 2 × F n − 2

因此对于 Fn F n ，我们有了递推公式 Fn=2n×Fn−1−(n−1)2×Fn−2 F n = 2 n × F n − 1 − ( n − 1 ) 2 × F n − 2

AC 代码

#include #define IO \ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0);using namespace std;typedef long long LL;const int maxn = 1e7 + 10;const int mod = 1e9 + 7;LL mul[maxn];LL inv[maxn];LL F[maxn];void init(){ mul[0] = 1; for (int i = 1; i < maxn; i++) mul[i] = (mul[i - 1] * i) % mod; inv[0] = inv[1] = 1; for (int i = 2; i < maxn; i++) inv[i] = (LL)(mod - mod / i) * inv[mod % i] % mod; for (int i = 1; i < maxn; i++) inv[i] = (inv[i - 1] * inv[i]) % mod; F[0] = 1; F[1] = 2; for (int i = 2; i < maxn; i++) { F[i] = 2LL * i * F[i - 1] % mod - 1LL * (i - 1) * (i - 1) % mod * F[i - 2] % mod; F[i] = (F[i] % mod + mod) % mod; }}LL C(int n, int m){ return mul[n] * inv[m] % mod * inv[n - m] % mod;}LL A(int n, int m){ return mul[n] * inv[n - m] % mod;}void solve(int n){ LL ans = 0; for (int i = 0; i <= n; i++) { ans += ((i & 1) ? -1LL : 1LL) * C(n, i) * A(n, i) % mod * F[n - i] % mod * F[n - i] % mod; ans = (ans % mod + mod) % mod; } cout << ans << endl;}int main(){#ifndef ONLINE_JUDGE freopen("test.in", "r", stdin); freopen("test.out", "w", stdout);#else IO;#endif // ONLINE_JUDGE init(); int n; while (cin >> n) solve(n); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。