先 % 一发题解里的微积分神仙们

Problem

https://www.luogu.org/problemnew/show/P3343

Solution

为什么写这篇题解呢，因为感觉里面的东西都很典型想总结一下...

子问题 1：统计一个联通块有多少种不连通方案 -> 状压 dp

子问题 2：一个经典的期望问题

从原问题到子问题 2 再到子问题 1 是一个很厉害的转化思路呢

因为数据范围很小所以怎么写都行呢

回来写了，因为很重要。

若加入了第 $k$ 条边后图联通，则答案为 $\frac{k}{m+1}$。

则若加入第 $k$ 条边后图 不联通 的概率为 $p_k$，则其对答案的贡献是 $\frac{1}{m+1}$。

即，$p_k$ 相当于贡献 $\frac{k}{m+1}-\frac{k-1}{m+1}$ 产生这个事件发生的概率。

这是一个非常经典的期望问题。

因此答案则为 $\frac{1}{m+1} \sum \limits_{k=0}^{m} p_k$。现在考虑如何求 $p_k$。

令 $f_{i,j}$ 为点集为 $i$，选了 $j$ 条边的不联通方案数。
$g_{i,j}$ 联通方案数。

显然有：$f_{i,j}+g_{i,j}=\binom{cnt_i}{j}$，其中 $cnt_i$ 为状态 $i$ 点集内包含的边数。

转移的话，我们考虑枚举一个定点和其所属联通块 $S$。则转移：
$$f_{S, i+j}=\sum \limits_{T\subset S} g_{T,i}*\binom{cnt_{S-T}}{j}$$

则 $p_k=\frac{f_{all, k}}{C(cnt_{all},k)}$

Code

// Code by ajcxsu
// Problem: after earthquake

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=110, T=1<<11;
ll c[N][N];
ll C(int i, int j) {
    if(i==j || j==0) return 1;
    if(i<j) return 0;
    if(c[i][j]!=-1) return c[i][j];
    return c[i][j]=C(i-1, j-1)+C(i-1, j);
}
char e[N][N];

ll f[T][N], g[T][N];
int cnt[T];

int main() {
    memset(c, -1, sizeof(c));
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    cin>>n>>m;
    int u, v;
    for(int i=0;i<m;i++) cin>>u>>v, u--, v--, e[u][v]=e[v][u]=1;
    int U=1<<n;
    for(int i=0;i<U;i++) {
        for(int u=0;u<n;u++)
        for(int v=u+1;v<n;v++)
            if(((1<<u)&i) && ((1<<v)&i) && e[u][v])
                cnt[i]++;
    }
    for(int i=0;i<U;i++)
        for(int j=0;j<=cnt[i];j++) {
            if(!i) g[i][j]=1;
            else {
                int k=1, S;
                for(;!(k&i); k<<=1);
                S=i^k;
                if(S) {
                    for(int T=(S-1)&S; T; T=(T-1)&S)
                        for(int l=0;l<=j;l++)
                            f[i][j]+=g[T|k][l]*C(cnt[i-T-k], j-l);
                    for(int l=0;l<=j;l++)
                        f[i][j]+=g[k][l]*C(cnt[i-k], j-l);
                }
                g[i][j]=C(cnt[i], j)-f[i][j];
            }
        }
    double ans=0;
    for(int i=0;i<=m;i++) ans+=1.0*f[U-1][i]/C(cnt[U-1],i);
    ans/=m+1;
    printf("%.6lf\n", ans);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-3343.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆