6979.【2021.02.03冬令营模拟】天各一方(far)

 

\(Description\)

给定一张大小为 \(n\) 的 联通 无向图，任意两座不同城市间可能存在道路，求对于所有可能的道路分布，从 \(1\) 到 \(n\) 的最短路长度之和模 \(p\)。

\(2 \leq n \leq 400, \ 10^6 \leq p \leq 10^9 + 9\)

 

\(Solution\)

首先可以发现到节点 \(2, \ 3, \ 4 \ ... \ n\) 是等价的，所以可以求出 \(1\) 到所有节点的距离和，最后除以 \(n - 1\)。

考虑对于一张固定的图如何求 \(1\) 到所有节点的距离和，有一种方法是 \(BFS\)，将原图分层。我们又知道对于任意一张图其分层方式唯一，所以这启示我们可以对分层方式 \(dp\)。

设 \(f_{i, j}\) 表示 \(i\) 个点的图，最后一层有 \(j\) 个点的方案数，\(g_{i, j}\) 表示所有方案的距离之和。考虑枚举下一层的点数 \(k\) 转移，\(f_{i, j}\) 对 \(f_{i + k, k}\) 的贡献次数为 \(C_{i + k - 1}^{k} (2^j - 1)^k 2^{k(k - 1) / 2}\)。为了转移 \(g\)，设辅助数组 \(h_{i, j}\) 表示所有分层方案的层数之和，那么总的转移就是

\[s = C_{i + k - 1}^{k} (2^j - 1)^k 2^{k(k - 1) / 2} \\[2ex] f_{i + k, k} = f_{i, j} \cdot s \\[2ex] g_{i + k, k} = (f_{i, j} + h_{i, j} \cdot k) \cdot s \\[2ex] h_{i + k, k} = (h_{i, j} + f_{i, j}) \cdot s \]

最后答案即为 \(\sum{g_{n, i}}\)。

 

\(Code\)

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define N 400
#define M 79800

#define ll long long

#define fo(i, x, y) for(int i = x, end_##i = y; i <= end_##i; ++ i)
#define fd(i, x, y) for(int i = x; i >= y; -- i)

ll f[N + 1][N + 1], g[N + 1][N + 1], h[N + 1][N + 1];

ll jc[N + 1], inv[N + 1], mi[M + 1], s[N + 1][N + 1];

int n, mo;

ll Fast(ll x, int p) {
    ll res = 1;
    while (p) {
        if (p & 1) res = res * x % mo;
        x = x * x % mo;
        p >>= 1;
    }
    return res;
}

ll C(int x, int y) { return jc[x] * inv[y] % mo * inv[x - y] % mo; }

int main() {
    freopen("far.in", "r", stdin);
    freopen("far.out", "w", stdout);

    scanf("%d %d", &n, &mo);

    jc[0] = mi[0] = 1;
    fo(i, 1, n) jc[i] = jc[i - 1] * i % mo;
    inv[n] = Fast(jc[n], mo - 2);
    fd(i, n, 1) inv[i - 1] = inv[i] * i % mo;
    fo(i, 1, M) mi[i] = mi[i - 1] * 2 % mo;
    fo(i, 1, n) fo(j, 1, n)
        s[i][j] = Fast(mi[i] - 1, j);
    

    f[1][1] = h[1][1] = 1, g[1][1] = 0;
    fo(i, 1, n - 1) fo(j, 1, i) {
        fo(k, 1, n - i) {
            ll d = C(i + k - 1, k) % mo * s[j][k]% mo * mi[k * (k - 1) >> 1] % mo;
            (f[i + k][k] += f[i][j] * d % mo) %= mo;
            (g[i + k][k] += (g[i][j] + h[i][j]* k % mo) * d % mo) %= mo;
            (h[i + k][k] += (h[i][j] + f[i][j]) % mo * d % mo) %= mo;
        }
    }
    ll ans = 0;
    fo(i, 1, n - 1) (ans += g[n][i]) %= mo;
    printf("%lld\n", ans * Fast(n - 1, mo - 2) % mo);

    return 0;
}