算法
(分层图dp) $O(N^3)$
记 dp[i][j]
表示在由 $i$ 个点构成的连通图中,距离顶点 $1$ 的最远点的有 $j$ 个(其实就是分层图的最后一层有 $j$ 个点)的图的个数
转移:
往当前分层图中添加 $k$ 个点时,将这 $k$ 个点安排在下一层
- 给每个点选择父节点的方案数为 $2^j-1$ 种(每个点至少要选择一个父节点)
- 这 $k$ 个点之间的连边方案数为 $2^{\frac{k(k-1)}{2}}$ 种
- 给这 $k$ 个点编号的方案数有 $\binom{N-1-i}{k}$ 种 (这里 $N-1$ 是因为点 $N$ 显然应该要放在最后一层)
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using mint = modint;
mint dp[505][505];
mint c[505][505];
int main() {
int n, m;
cin >> n >> m;
mint::set_mod(m);
vector<mint> two(n*n+1, 1);
rep(i, n*n) two[i+1] = two[i]*2;
auto c2 = [](int n) { return n*(n-1)/2; };
c[0][0] = 1;
rep(i, n)rep(j, i+1) {
c[i+1][j] += c[i][j];
c[i+1][j+1] += c[i][j];
}
dp[1][1] = 1;
rep(i, n)rep(j, n) {
mint now = dp[i][j];
if (now == 0) continue;
for (int nj = 1; i+nj <= n-1; ++nj) {
int ni = i+nj;
mint co = two[c2(nj)];
co *= (two[j]-1).pow(nj);
co *= c[n-1-i][nj];
dp[ni][nj] += now*co;
}
}
mint ans;
rep(j, n) {
mint now = dp[n-1][j];
if (now == 0) continue;
mint co = two[j]-1;
ans += now*co;
}
cout << ans.val() << '\n';
return 0;
}