【Luogu】P3343地震后的幻想鄉（對積分概率進行DP）

　　題目鏈接

　　神難qwq。配合rqy的博客食用。

　　首先我們學到有一個概率函數$p(x)$表示某事件發生概率取值小于x的函數。這個函數有什么特點呢？

　　那就是$\int_{-∞}^{∞}p(x)dx=1$

　　這個是顯然的

　　然后我們令p(x)為首次聯通的時間的概率分布函數

　　這其實等價于生成樹的最大權邊等于x的概率，對不對（我虛啊，我很可能理解錯的）

　　然后呢，就有一個期望的式子

　　$EX=\int tp(t)dt$

　　我忘了是為什么了（上午rqy才剛給我講過，現在就忘了），我太菜了。

　　然后本題中，期望就是$EX=\int_{0}^{1}xp(x)dx$

　　$=\int_{0}^{1}p(x)( \int_{0}^{x}1ds)dx$

　　$=\int_{0}^{1}(\int_{s}^{1}p(x)dx)ds$

　　然后我們把括號里面那個玩意設成P(s)好了

　　所以原式被我們化成了$\int_{0}^{1}P(s)ds$

　　然后……emm等一會我忘了我要干嘛了qwq

　　……
　　然后我們設一個$f_{x,S}$表示集合S（S包含1節點）在x時刻前不連通，x時刻恰好聯通的概率

　　因為在x時刻不連通，所以我們考慮它的轉移

　　$f_{x,S}=\sum\limits_{1屬于S'}^{S'包含于S}(1-f_{x,S'})(1-x)^{T(S',S-S')}$

　　這什么意思呢？

　　我們設T(A,B)為A點集和B點集之間的邊數。

　　首先我們看見里面有一個$(1-f_{x,S'})$，這個玩意的意思是

　　既然我們的S集合要恰好聯通，那在這之前S'作為S的一個子集是一定要聯通的。而f表示的是不連通的概率，所以就是1-x唄。

　　而且S'和外界不要聯通。

　　既然S和外界不要聯通，那每條邊在x時刻不連通的概率是(1-x)，那T條邊都不連通的概率就是$(1-x)^{T(S',S-S')}$

　　所以說$f_{x,S'}$就是這么一個玩意兒。

　　然后我們把x當成參，就有了$f_{S'}(x)$這么一個東西。

　　然后……比如說有個全集U

　　最后我們求的就是這么一個玩意

　　$\int_{0}^{1}f_{U}(x)dx$

　　然后下面的我就全忘了，順著rqy的筆跡講，不過我自己也看不懂是在干嘛qwq

　　我們設$dp_{S,k}=\int_{0}^{1}f_{S}(x)(1-x)^{k}dx$

　　$=\int_{0}^{1}(\sum\limits_{1屬于S'}^{S'包含于S}(1-f_{S'}(x))(1-x)^{T(S',S-S')})(1-x)^{k}dx$

　　設t=T(S',S-S')

　　$dp_{S,k}=\sum\limits_{1屬于S'}^{S'包含于S}\int_{0}^{1}(1-f_{S'}(x))(1-x)^{t+k}dx$

　　$=\sum\limits_{1屬于S'}^{S'包含于S}\int_{0}^{1}(1-x)^{t+k}-f_{S'}(x)(1-x)^{t+k}dx$

　　我們發現后面那個玩意等于$dp_{S',t+k}$

　　就可以搞啦。至于k到底干嘛的，rqy說不表示實際意義，只是用來簡化計算，我沒聽懂。qwq

　　最后求的答案就是$dp_{U,0}$

　　然后就是遞歸搞一搞DP輸出。

　　（當然到考場上如果碰到這道題我傾向于手玩。智商-INFqwq。）

　　

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cstdlib>
#define maxn 11
#define maxm 55
inline long long read(){long long num=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')    f=-1;ch=getchar();}while(isdigit(ch)){num=num*10+ch-'0';ch=getchar();}return num*f;
}double f[1<<maxn][maxm];
int q[1<<maxn][1<<maxn];
bool vis[1<<maxn][maxm];double dfs(int state,int t){if(state==1)    return 0;if(vis[state][t])    return f[state][t];vis[state][t]=1;double &ans=(f[state][t]=.0);for(int sta=(state-1)&state;sta!=state;sta=(sta-1)&state)if(sta&1){ans+=1.0/(t+q[sta][state&(~sta)]+1);ans-=dfs(sta,t+q[sta][state&(~sta)]);}return ans;
}int main(){int n=read(),m=read();int Max=1<<n;for(int i=1;i<=m;++i){int a=read(),b=read();a--;b--;for(int sta=0;sta<Max;++sta){if(((sta>>a)&1)==0)    continue;for(int stb=0;stb<Max;++stb){if(((stb>>b)&1)==0)    continue;q[sta][stb]++;    q[stb][sta]++;}}}printf("%.6lf",dfs(Max-1,0));return 0;
}

?