「模擬賽20180406」膜樹 prufer編碼+概率

題目描述

給定一個完全圖，保證\(w_{u,v}=w_{v,u}\)且\(w_{u,u}=0\)，等概率選取一個隨機生成樹，對於每一對\((u,v)\)，求\(dis(u,v)\)的期望值對\(998244353\)取模。

輸入

第一行一個數\(n\)

接下來\(n\)行，每行\(n\)個整數，第\(i\)行第\(j\)個整數表示\(w_{i,j}\)

輸出

輸出共\(n\)行，每行\(n\)個整數，第\(i\)行第\(j\)個整數表示\(dis(i,j)\)的期望值

樣例

樣例輸入

4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

樣例輸出

0 374341634 374341634 374341634
374341634 0 374341634 374341634
374341634 374341634 0 374341634
374341634 374341634 374341634 0

數據範圍

\(\left|w_{i,j}\right| \leq 10^9\)

\(n \leq 1000\)

題解

這是一道神奇的概率題……

其實題目原來是有一個\(20%\)的數據點，此時\(n\leq 9\)，顯然我們可以用\(prufer\)編碼枚舉生成樹，然後暴力算答案即可（\(QwQ\)卡常拿了\(15pts\)走人）。但是顯然\(1000\)是不可能的……

於是我們考慮這道題的特殊性質——這是一個完全圖！完全圖擁有非常好的對稱性！
根據上面這點，對於點對\((u,v)\)，任意的一條邊\((x,y)\)出現在\(u\)到\(v\)的路徑上的概率是一樣的，同理，任意一條邊\((u,x)\)或\((x,v)\)出現在\(u\)到\(v\)的路徑上的概率也是一樣的。於是我們發現可以把邊分成三類。

1. \((u,v)\)，即兩端點都在路徑上
2. \((u,x)\)或\((x,v)\)，即有一個端點在路徑上
3. \((x,y)\)，即兩端點都不在路徑上

對於第一種，只要這條邊出現在生成樹中就一定會經過，於是就是某一條邊出現在生成樹中的概率。生成樹有\(n^{n-2}\)種，每種會給\((n-1)\)條邊帶來\(1\)貢獻，顯然每條邊的總貢獻是相同的，於是單條邊的貢獻為\(\frac{n^{n-2}\cdot(n-1)}{\frac{n\cdot(n-1)}{2}}=2\cdot n^{n-3}\)
然後只需再除以總方案數\(n^{n-2}\)就是概率，即\(\frac{2}{n}\)

考慮第二種，顯然對於所有的\((u,x)\)概率都相等……可以發現，如果\((u,v)\)存在生成樹中，一定不會選到\((u,x)\)，否則就等概率地選中\((u,x)\)。那麼答案為\(\frac{1-\frac{2}{n}}{n-2}\)

第三種不容易看出什麼特征了，我們暴力一點求。假設把這條邊切斷，發現左右分成兩部分，我們可以枚舉其中\(x\)部分的大小，設為\(i\)，則\(y\)部分為\(n-i\)，其中有\(4\)個點已經確定了——\(x,y,u,v\)，為了方便，我們固定\(u\)在\(x\)這邊，而\(v\)在\(y\)這邊，最後答案乘\(2\)即可（交換\(u,v\)）。顯然，答案需要乘上\(C_{n-4}^{i-2}\)，\(n-4\)是因為除去這四個點，\(i-2\)是除去\(x\)和\(u\)。然後左右兩邊的任意一個無根樹形態都是可以的，根據\(prufer\)編碼，答案就是： \[\sum_{i=2}^{n-2}{\cfrac{2\cdot i^{i-2}\cdot(n-i)^{n-i-2}\cdot C^{n-4}_{i-2}}{n^{n-2}}}\]直接\(O(n\log n)\)求就好了

然後統計答案，註意各種小細節，這道題就\(A\)掉辣！

\(Code:\)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 1005
#define mod 998244353
int n, dis[N][N], nei[N], all;
int fir, sec, thi;
int fac[N], inv[N];
int ksm(int a, int k)
{
    if (!k)
        return 1;
    int p = ksm(a, k / 2);
    if (k & 1)
        return 1ll * a * p % mod * p % mod;
    return 1ll * p * p % mod;
}
int div(int a){return ksm(a, mod - 2);}
int tree(int a)
{
    if (a == 1)
        return 1;
    return ksm(a,  a - 2);
}
int C(int n, int m)
{
    return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main()
{
    fac[0] = 1;
    for (int i = 1; i <= N - 5; i++)
        fac[i] = 1ll * fac[i - 1] * i % mod;
    inv[N - 5] = ksm(fac[N - 5], mod - 2);
    for (int i = N - 5; i >= 1; i--)
        inv[i - 1] = 1ll * inv[i] * i % mod;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &dis[i][j]);
            if (i < j)
                all = (all + dis[i][j]) % mod;
            nei[i] = (nei[i] + dis[i][j]) % mod;
        }
    fir = 2 * div(n) % mod;
    sec = 1ll * (1 - fir) * div(n - 2) % mod;
    if (sec < 0)
        sec += mod;
    for (int i = 1; i < n - 2; i++)
    {
        int j = n - 2 - i;
        thi = (thi + 2ll * tree(i + 1) * tree(j + 1) % mod * C(n - 4, i - 1) % mod) % mod;
    }
    thi = 1ll * thi * div(tree(n)) % mod;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            int ans = 1ll * dis[i][j] * fir % mod;
            ans = (ans + 1ll * ((nei[i] + nei[j]) % mod - dis[i][j] * 2) % mod * sec % mod) % mod;
            ans = (ans + 1ll * (all - ((nei[i] + nei[j]) % mod - dis[i][j]) % mod) * thi % mod) % mod;
            if (ans < 0)
                ans += mod;
            if (i == j)
                ans = 0;
            printf("%d%c", ans, j == n ? 10 : 32);
        }
}