【状压+期望DP,定积分】BZOJ3925 [Zjoi2015]地震后的幻想乡

以下是ChesterKing神仙的题解:

题目传送门

这题是真的神仙题……整整花了我两个礼拜来理解这题

首先这题据我了解有三种做法:纯OI做法、积分+数学推导、直接积分

请做好一定的心理准备,接下来的东西可能有点难理解(好像不是一点点的难吧……)


1.纯OI做法

首先我们根据期望的线性性,可以得到\(ans=\sum_{x=0}^mw(x)\times p(x)\),其中\(w(x)\)为最大边为\(x\)时的对答案的贡献,\(p(x)\)为最大边为\(x\)时的概率。

由题目所给信息“对于\(n\)个之\([0,1]\)间的随机变量\(x1,x2,...,xn\),第\(k\)小的那个的期望值是\(\frac{k}{n+1}\)”可知:\(w(x)=\frac{x}{m+1}\)

\(\therefore ans=\sum_{x=0}^m\frac{x}{m+1}\times p(x)\)

\(f(x)\)为最大边权的排名\(\ge x\)的概率,则\(p(x)=f(x-1)-f(x)\)

\[ \therefore ans=\frac{1}{m+1}\times[f(0)-f(1)]+\frac{2}{m+1}\times[f(1)-f(2)]+...+\frac{m}{m+1}\times[f(m-1)-f(m)]+\frac{m+1}{m+1}\times[f(m)-f(m+1)] \]

\(\because f(0)=1,f(m+1)=0\) \[ \therefore ans=\frac{1}{m+1}\sum_{x=0}^mf(x) \] 定义\(f[S][i]\)为点集为\(S\),选取了\(i\)条边使得点集不连通的方案数;同理,定义\(g[S][i]\)为点集为\(S\),选取了\(i\)条边使得点集连通的方案数。

易得\(f[S][i]+g[S][i]={i\choose cnt[s]}\),其中\(cnt[S]\)为点集\(S\)内的边数。

可以通过固定某定点\(P\)来进行转移,以达到不重复、不遗漏的计数。 \[ f[S][i+j]=\sum_{P \in S,T \subset S}g[T][i]\times{j \choose cnt[S-T]} \] 那么最终答案即为\(ans=\frac{1}{m+1}\sum_{x=0}^m\frac{f[all][x]}{x \choose cnt[all]}\)

附上AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
using namespace std;

typedef long long ll;
const int N=11,M=46;
int n,m,e[N],sz[1<<N],cnt[1<<N],wz;
ll c[M][M],f[1<<N][M],g[1<<N][M];
double ans;

int main(void){
scanf("%d%d",&n,&m);
for (int i=1,x,y; i<=m; ++i) scanf("%d%d",&x,&y),--x,--y,e[x]|=1<<y,e[y]|=1<<x;
c[0][0]=1;
for (int i=1; i<=m; ++i){
c[i][0]=1;
for (int j=1; j<=i; ++j) c[i][j]=c[i-1][j-1]+c[i-1][j];
}
for (int sub=1; sub<(1<<n); ++sub){
if ((sz[sub]=sz[sub>>1]+(sub&1))==1){g[sub][0]=1; continue;}
for (int i=0; i<n; ++i) if ((sub>>i)&1) cnt[sub]+=sz[e[i]&sub];
cnt[sub]>>=1,wz=sub&-sub;
for (int opt=(sub-1)&sub; opt; opt=(opt-1)&sub)
if (opt&wz)
for (int i=0; i<=cnt[opt]; ++i)
for (int j=0; j<=cnt[opt^sub]; ++j)
f[sub][i+j]+=g[opt][i]*c[cnt[opt^sub]][j];
for (int i=0; i<=cnt[sub]; ++i) g[sub][i]=c[cnt[sub]][i]-f[sub][i];
}
for (int i=0; i<=m; ++i) ans+=(double)f[(1<<n)-1][i]/c[cnt[(1<<n)-1]][i];
return printf("%.6lf\n",ans/=m+1),0;
}

接下来的两种做法可能需要一定的高等数学知识,至于定积分、求导之类的运算法则,出门左拐度娘处。

讲接下来的两种做法之前,我们先来证明一个对于我个人很难理解的东西,因为接下来的做法都要用到。

求证:\(ans=\int_0^1f(x){\rm d}x\),其中\(f(x)\)为答案\(>x\)的概率。

证明:设\(p(x)\)为答案\(=x\)的概率

易得:\(p(x)=\lim_{\Delta x \rightarrow 0}\frac{f(x)-f(x+\Delta x)}{\Delta x}=-f'(x)\)

根据期望的定义,得:\(ans=\int_0^1x\times p(x){\rm d}x\)

\[ \begin{align} \therefore ans&=\int_0^1x\times (-f'(x)){\rm d}x\\ &=\int_0^1x{\rm d}(-f(x))\\ &=[x\times (-f(x))]_0^1+\int_0^1f(x){\rm d}x \end{align} \] \(\because f(x)\)为答案\(>x\)的概率\(\qquad\therefore f(0)=1,f(1)=0\qquad\therefore ans=\int_0^1f(x){\rm d}x\)

证毕。

2.积分+数学推导

我们设一个函数\(P_S(t)\)表示当\(S\)[\(S\)为一个点集在原图中的导出子图]中的最大边为\(t\)时,\(S\)不连通的概率为\(P_S(t)\)

那么有\(E(X)=\int_0^1P_{SIE}(t){\rm d}t\qquad\)[\(SIE\)为全集]\(\qquad\)(根据上面的证明可得)

我们可以方便地写出\(P(t)\)的递归式。

我们考虑一张图\(S\),我们把其分成两部分(\(S_0\)\(S-S_0\)),那么\(S_0\)连通而\(S\)不连通的概率为: \[ [1-P_{S_0}(t)]\times(1-t)^{E(S_0,S)} \] 其中\(E(S_0,S)\)\(S_0\)\(S- S0\)的边数。 \[ \begin{align} \therefore P_S(t)&=\sum_{S_0\not\subseteq S}(1-t)^{E(S_0,S)}\times [1-P_{S_0}(t)]\qquad[1\in S_0]\\ \therefore E(X)&=\int_0^1P_{SIE}(t){\rm d}t\\ &=\int_0^1\sum(1-t)^{E(S_0,S)}\times[1-P_{S_0}(t)]]{\rm d}t\qquad[1\in S_0)]\\ &=\sum\int_0^1(1-t)^{E(S_0,S)}{\rm d}t-\int_0^1(1-t)^{E(S_0,S)}\times P_{S_0}(t){\rm d}t\\ &=\sum\frac{1}{E(S_0,S)+1}-\int_0^1(1-t)^{E(S_0,S)}\times P_{S_0}(t){\rm d}t \end{align} \]

我们递归定义\(f[S_0][E(S_0,S)]=\int_0^1(1-t)^{E(S_0,S)}\times P_{S_0}(t){\rm d}t​\)

\(\therefore f[1][k]=0,k\in[0,m]\qquad f[S][k]=\sum\frac{1}{k+E(S_0,S)+1}-f[S_0][k+E(S_0,S)]\)

然后直接暴力即可。

附上AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
using namespace std;

const int N=11,M=56;
int n,m,x,y,t[1<<N][1<<N],all,b[1<<N][M];
double f[1<<N][M];

inline double calc(int sub,int k){
if (sub==1) return 0;
if (b[sub][k]) return f[sub][k];
b[sub][k]=1;
double &ans=(f[sub][k]=.0);
for (int opt=(sub-1)&sub; opt^sub; opt=(opt-1)&sub)
if (opt&1) ans+=1.0/(k+t[opt][sub&~opt]+1),ans-=calc(opt,k+t[opt][sub&~opt]);
return ans;
}

int main(void){
scanf("%d%d",&n,&m),all=(1<<n)-1;
while (m--){
scanf("%d%d",&x,&y),--x,--y;
for (int s1=0; s1<=all; ++s1)
if ((s1>>x)&1)
for (int s2=0; s2<=all; ++s2)
if ((s2>>y)&1)
++t[s1][s2],++t[s2][s1];
}
return printf("%.6lf\n",calc(all,0)),0;
}

3.直接积分

首先记\(F(x)\)为答案\(>x\)的概率,可知\(ans=\int_0^1F(x){\rm d}x\)

\(F(x)\)等价于边权\(<x\)时不能使图连通的概率。有点难求,正难则反,考虑使图连通的概率。

\(f(S)\)为集合\(S\)连通的概率,\(f(S)=1-\sum_{S'\subset S}f(S')\times(1-x)^{cnt}\),其中\(cnt\)\(S'\)\(S-S'\)的边数。

可以发现,\(f(S)\)为关于\(x\)的多项式,可以做定积分。

也可以换一种理解的方式。

\(f(x)\)\(x==ans\)的概率密度函数,令\(F(x)=\int f(x){\rm d}x\) \[ \begin{align} ans&=\int_0^1xf(x){\rm d}x\\ &=\int_0^1x{\rm d}(F(x))\\ &=[x\times F(x)]_0^1-\int_0^1F(x){\rm d}x\\ &=1-\int_0^1F(x){\rm d}x\\ &=\int_0^1(1-F(x)){\rm d}x \end{align} \] \(F(x)\)的意义为取值\(\le x\)的概率,等价于每条边有\(x\)的概率出现,问图的连通概率。

注意:这种做法不知为何有点卡精度,需要开__float128。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <vector>
using namespace std;

const int N=10,M=57;
typedef __float128 ld;
typedef long long ll;
typedef vector <ll> poly;
struct note{
int x,y;
}a[M];
int n,m;
poly o,tmp,f[1<<N],ans;

inline bool in(int x,int sub){return (sub>>x-1)&1;}

inline poly operator * (const poly x,const poly y){
poly ret(x.size()+y.size()-1,0);
for (int i=0; i<x.size(); ++i)
for (int j=0; j<y.size(); ++j)
ret[i+j]+=x[i]*y[j];
return ret;
}

inline poly operator - (const poly x,const poly y){
poly ret(max(x.size(),y.size()),0);
for (int i=0; i<x.size(); ++i) ret[i]+=x[i];
for (int i=0; i<y.size(); ++i) ret[i]-=y[i];
return ret;
}

inline ld integrate(poly ans){
ld ret=0;
for (int i=0; i<ans.size(); ++i) ret+=ld(1.0)*ans[i]/(i+1);
return ret;
}

int main(void){
scanf("%d%d",&n,&m);
for (int i=1; i<=m; ++i) scanf("%d%d",&a[i].x,&a[i].y);
o.push_back(1),o.push_back(-1),f[1].push_back(1);
for (int sub=3; sub<(1<<n); sub+=2){
f[sub].clear(),f[sub].push_back(1);
for (int opt=(sub-1)&sub; opt; opt=(opt-1)&sub)
if (opt&1){
int cnt=0;
for (int i=1; i<=m; ++i)
if (in(a[i].x,sub)&&in(a[i].y,sub)&&(in(a[i].x,opt)^in(a[i].y,opt))) ++cnt;
for (tmp=f[opt]; cnt; --cnt) tmp=tmp*o;
f[sub]=f[sub]-tmp;
}
}
ans.push_back(1),ans=ans-f[(1<<n)-1];
return printf("%.6f\n",(double)integrate(ans)),0;
}

后记:讲真,这的确是一道神题,很有思考的价值。

还有一小部分没有弄懂,就是“对于\(n\)个之\([0,1]\)间的随机变量\(x1,x2,...,xn\),第\(k\)小的那个的期望值是\(\frac{k}{n+1}\)”的证明,最近还在思考,挖坑待填。

连续性变量的期望用微积分的方法来做会简便很多。

希望我写的博客能够帮助各位巨佬解这道题,另外我不觉得信息学和微积分有何冲突,只要是能做题的方法都是好方法,并没有哪种方法好一些,不应该有偏见,能掌握做题的方法肯定是越多越好。

就这样吧。