欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

「模拟赛20180406」膜树 prufer编码+概率

程序员文章站 2022-07-05 11:38:20
题目描述 给定一个完全图,保证$w_{u,v}=w_{v,u}$且$w_{u,u}=0$,等概率选取一个随机生成树,对于每一对$(u,v)$,求$dis(u,v)$的期望值对$998244353$取模。 输入 第一行一个数$n$ 接下来$n$行,每行$n$个整数,第$i$行第$j$个整数表示$w_{ ......

题目描述

给定一个完全图,保证\(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);
        }
}