[题解] [BZOJ2169] 连边

佚名 4年前 (2020-01-17) 随笔 1452人围观抢沙发百度已收录

题面

题解

看到数据范围很容易想到 DP 方程式

设 \(f[i][j]\) 代表已经连了 \(i\) 条边, 还有 \(j\) 个奇数点, 并且方案全部合法的方案数

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

那么有
\[ \displaystyle \begin{aligned}f[i][j] = &f[i - 1][j + 2]*\binom{j+2}{2}\\+&f[i - 1][j - 2]*\binom{n-j+2}{2}\\+&f[i - 1][j]*(n-j)*j\end{aligned} \]
分别代表连两个奇数点, 两个偶数点, 一个奇数点一个偶数点

注意一下边界即可

但是问题在这里, 这次连的边有可能与之前新连的某一条边重合, 这样方案就不合法了, 我们可以强制这两条边是先后连的

因为我们求的是连边的方案, 没有顺序, 所以这样不会对答案造成影响

即
\[ \displaystyle f[i][j] -= f[i - 2][j]*(\binom{n}{2}-(i-2)) \]
这两条边先后连, 所以在这之前已经连了 \(i - 2\) 条边, 这条边可能连在任意两个点中间, 但是不能与之前的那 \(i - 2\) 条边相重复了, 因为实际上我们是把 DP 的两步转移并做了一步, 若与之前的 \(i - 2\) 条边重合了, 那么在第一次转移后的 \(f\) 就不符合全部合法的定义了

除此之外, 每次转移完之后都要除以 \(i\) , 因为方案是无序的

举一个例子, 比如说上次我们连边的方案分别是 \((1, 2)\) , \((2, 3)\) , \((1, 3)\)

若这次我们分别连上 \(3\) , \(1\) , \(2\) , 那么三种方案最终都是 \((1, 2, 3)\) , 重复了

所以要除去 \(i\)

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 1005;
const int mod = 10007; 
using namespace std;
 
int n, m, k, d[N], c[N][N], f[N][N], inv[N], cnt; 
 
template < typename T >
inline T read()
{
    T x = 0, w = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * w; 
}
 
int main()
{
    n = read <int> (), m = read <int> (), k = read <int> ();
    for(int i = 1; i <= m; i++)
        d[read <int> ()]++, d[read <int> ()]++;
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= i; j++)
            c[i][j] = (!j ? 1 : (c[i - 1][j] + c[i - 1][j - 1]) % mod);
    inv[1] = 1; 
    for(int i = 2; i <= k; i++)
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod; 
    for(int i = 1; i <= n; i++)
        if(d[i] & 1) cnt++; 
    f[0][cnt] = 1; 
    for(int i = 1; i <= k; i++)
        for(int j = 0; j <= n; j++)
        {
            if(j - 2 >= 0)
                f[i][j] = (f[i][j] + 1ll * f[i - 1][j - 2] * c[n - j + 2][2] % mod) % mod;
            if(j + 2 <= n)
                f[i][j] = (f[i][j] + 1ll * f[i - 1][j + 2] * c[j + 2][2] % mod) % mod;
            f[i][j] = (f[i][j] + 1ll * f[i - 1][j] * j % mod * (n - j) % mod) % mod;
            f[i][j] = (f[i][j] - 1ll * f[i - 2][j] * (c[n][2] - i + 2) % mod + mod) % mod;
            f[i][j] = 1ll * f[i][j] * inv[i] % mod; 
        }
    printf("%d\n", f[k][0]); 
    return 0; 
}