【ABC253Ex】We Love Forest 题解

图上计数

Statement

给定一张有 \(n\) 个点，没有边的图

给定 \(m\) 条可能存在的边，有 \(k\) 次机会，每次可以等概率地抽取一条边并加入，同一条边可以被加入多次，\(m\) 条边中可能存在重边

对于每一个 \(k=1,2,\dots,n-1\) ，求出得到的图为森林的概率

\(n\le 14,n-1\le m\le 500\)

Solution

思路来自 https://atcoder.jp/users/GidroOttenok3797

概率直接转方案数

看到 \(n\le 14\)， 想到这应该是一个带 \(2^n\) 复杂度的解法

考虑设 \(g[i][S]\) 表示 \(i\) 步过后，\(s\) 集合成为森林的方案数，

考虑转移，按照围绕一个基准点构造一个整体的思想，我们固定集合之中最小的点，dia 出一棵包含 \(lowbit(S)\) 的树来

\[g[i][S]=\sum_{lowbit(S)\in T\subseteq S} g[i-|T|+1][S/T]\times f[T] \]

其中 \(f[T]\) 表示 \(T\) 集合成为一棵树的方案数（花费 \(|T|-1\) 次机会），那么

\[f[S]=\begin{cases} 1,& |S|=1\\ \sum f[T]\times f[S/T]\times h(S,T),&otherwise \end{cases} \]

其中 \(h(S,T)\) 表示集合 \(S\) 和集合 \(T\) 的连边数量，容斥一下

\[h(S,T)=e(S|T)-e(S)-e(T) \]

其中 \(e(S)\) 表示 \(S\) 中的边的数量

这样的话，我们只需要 \(O(n2^n)\) 计算 \(e\) , \(O(3^n)\) 计算 \(f\) , \(O(n3^n)\) 计算 \(g\) 即可

答案为 \(\dfrac {g[i][2^n-1]\times i!}{m^i}\)

Code

#include
#define ppc(x) __builtin_popcount(x)
#define lowbit(x) (-x&x)
using namespace std;
const int mod = 998244353;
const int N = 15;
const int M = 505;

char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){
    int s=0,w=1; char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
    return s*w;    
}
int ksm(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=1ll*res*a%mod;
        a=1ll*a*a%mod,b>>=1;
    }
    return res;
}
void inc(int &a,int b){a=a>=mod-b?a-mod+b:a+b;}
void dec(int &a,int b){a=a>=b?a-b:a+mod-b;}
int add(int a,int b){return a>=mod-b?a-mod+b:a+b;}
int del(int a,int b){return a>=b?a-b:a+mod-b;}
 
int f[1<=ppc(k)-1)
                    inc(g[i][j],1ll*g[i-ppc(k)+1][j^k]*f[k]%mod);
        }
    
    for(int i=1;i