【题解】[ABC281G] Farthest City

好久没有写题解了，刷到了一道非常组合的题目。

Statement

给定整数 $N$ （$N \le 500$）和不固定模数 $M$，求出 $N$ 个点连出无向图的个数，满足顶点 $1$ 到 $N$ 的最短距离严格大于顶点 $1$ 到其他节点的最短距离。

Solution

模数不一定为质数，因此在得到模数之后再预处理组合数组。

首先固定节点 $1$ 和节点 $N$，$N$ 毫无疑问是唯一距离 $1$ 最远的一个点，因此考虑 $dist$ 从小到大进行转移。注意力惊人的话注意到边权为 $1$，因此可以将整幅图进行分层，然后就可以定义出 $dp_{i, j}$ 表示固定了前 $i$ 个点，最后一层有 $j$ 个点的方案总数。

显然每一个点只会在一层出现，答案即为 $dist_{N, 1}$。

考虑如何转移，首先遍历二维数组肯定是 $N^2$ 级别的。时间复杂度允许我们多一个 $N$ 用来枚举上一层有几个点，即 $dp_{i, j} \gets dp_{i - j, k}$​。

先考虑这 $j$ 个点怎么选，显然从剩下的 $(N - 1 - (i - j))$ 中去选，方案数为显然的：

$$\binom{N - 1 - (i - j)}{j}$$

接着考虑有多少种连边方式：

• 这一层的点互相连接，一共有 $j$ 个点，两两选择一共 $\tbinom{j}{2}$ 种选法，每一种选法有连和不连两种，因此这种方案数为：$2^{\tbinom{j}{2}}$。
• 上一层与这一层连接，枚举上一层有 $k$ 个点，对于这一层的每一个点，上一层一共有 $2^k$ 种选法，其中由于这两层必须有边，因此方案数减去 $1$。一共 $j$ 个点，乘法原理可得方案数为：$(2^k - 1) ^ j$。

综上，由于状态的转移必然是乘法原理，可以得出总的转移方程为：

$$dp_{i, j} = 2^{\tbinom{j}{2}}\binom{N - 1 - (i - j)}{j} \sum_{k = 1}^{i - j} (2 ^ k - 1) ^ j \times dp_{i - j, k}$$

预处理后的时间复杂度为 $O(N ^ 3)$，但是不处理也可以极限卡过。

1
2
3
4
5
6
7
8
9
10
11
12

dp[1][1] = 1;
for (int i = 2; i <= n; i ++)
{
    for (int j = 1; j < i; j ++)
    {
        mint temp = C[n - 1 - (i - j)][j];
        for (int k = 1; k <= i - j; k ++)
            dp[i][j] += temp * (mint(2).pow(k) - 1).pow(j) * dp[i - j][k];
        dp[i][j] *= mint(2).pow(C[j][2].val());
    }
}
cout << dp[n][1].val() << '\n';