HDOJ 5779 - Tower Defence

#数学 #计数 #图的计数
Published on 2016-08-02

题目地址

描述

一张有 n(n≤60)n(n\le 60) 个点的无向图（图可以不连通,没有重边和自环），所有边的长度都为 11，满足从 1 号点到其他任意一个点的最短路都不等于 k(k≤60)k(k\le 60)。如果两个顶点不连通，那么它们之间的距离为无穷大。
请问这样的图有多少个？答案对 10000000071000000007 取模。

分析

几乎图的计数问题都是用递推来解的，但分析题目发现，最短路是本题一个比较棘手的东西，不太好将其变为约束条件。
但是题目却有一个至关重要的信息，所有边的长度均为 11，对于长度均为 11 的图，我们从 1 号点 BFS 一次即可得到从 1 号点出发的最短路。注意到 BFS 入队顺序是按照最短路长度分层的，我们考虑逐层加点。
首先最短路不等于 kk，可以转化成最短路小于 kk。再者因为是只考虑从 1 出发的最短路，所以我们可以只求出 1 所在的联通块的情况，让剩余的点任意连边即可。

定义 fd,i,jf_{d, i, j} 为有 ii 个点的联通块（包含 1 号点），其中 1 号点到其他点的最长最短路是 dd，有 jj 个点到 1 号点的最长路是 dd。
转移怎么转移？利用分层思想，从最短路是 d−1d - 1 的点连向新的点，这样新的点的最短路就是 dd 了。
方程不难列出：

fd,i,j=∑1≤k≤i−jfd−1,i−j,k×(2k−1)j×2j(j−1)2×Ci−1jf_{d, i, j} = \sum_{1\le k\le i - j}f_{d - 1, i - j, k}\times(2^k-1)^j\times2^{\frac {j(j - 1)}{2}}\times C_{i - 1}^{j}

注意由 d−1d - 1 的 kk 个点连向 jj 个点的方案是 (2k−1)j(2^k-1)^j，因为 jj 个点中任意一个点被至少一条边连接的方案为 2k−12^k - 1。同时 jj 个点之间可以任意连边，最短路不受影响，同时我们需要考虑 jj 个点是哪 jj 个点，所以要乘一个组合数。

求出 fd,i,jf_{d, i, j} 后，对答案的贡献为从 n−1n-1 个点中选 i−1i-1 个点组成连通块大小为 ii 的方案（因为 1 号点一定在连通块内），乘上剩下 n−in-i 个点内部乱连的方案，贡献为 fd,i,j×Cn−1i−1×2(n−i)(n−i−1)2f_{d, i, j} \times C_{n - 1}^{i - 1} \times 2^{\frac{(n - i)(n - i - 1)}{2}}。

复杂度 O(kn3)O(kn^3)。

代码

//  Created by Sengxian on 8/2/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  HDOJ 5779 图的计数 DP
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 60 + 3, modu = 1000000007;
int n, K, c[maxn][maxn], g[maxn][maxn], powers[maxn * maxn];

inline void add(int &ans, const int &v) {
    ans += v;
    if (ans >= modu) ans -= modu;
}

int f[maxn][maxn][maxn];
inline int solve() {
    int ans = 0;
    memset(f, 0, sizeof f);
    f[0][1][1] = 1;
    for (int d = 1; d < K; ++d)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= i; ++j)
                for (int k = 1; k <= i - j; ++k)
                    add(f[d][i][j], (ll)f[d - 1][i - j][k] * g[j][k] % modu * powers[c[j][2]] % modu * c[i - 1][j] % modu);
    for (int d = 0; d < K; ++d)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= i; ++j) if (f[d][i][j])
                add(ans, (ll)f[d][i][j] * c[n - 1][i - 1] % modu * powers[c[n - i][2]] % modu);
    return ans;
}

int main() {
    c[0][0] = 1;
    for (int i = 1; i < maxn; ++i) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; ++j)
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % modu;
    }
    powers[0] = 1;
    for (int i = 1; i < maxn * maxn; ++i) powers[i] = (powers[i - 1] << 1) % modu;
    for (int i = 1; i < maxn; ++i) g[0][i] = 1;
    //j -> i
    for (int i = 1; i < maxn; ++i)
        for (int j = 1; j < maxn; ++j)
            g[i][j] = (ll)g[i - 1][j] * (powers[j] - 1) % modu;
    int caseNum = ReadInt();
    while (caseNum--) {
        n = ReadInt(), K = ReadInt();
        printf("%d\n", solve());
    }
    return 0;
}
BZOJ 4650 - [Noi2016]优秀的拆分