【概率与期望】【组合计数】TopCoder SRM 561 Orienteering

题意：

给出一颗树，树上有些选中点$C$，现在随机从中选择一个大小为$k$的子集$S$，计算出一条包含所有$S$中的点的最短路径$P$，求$P$的期望长度。

点数$N\le 2500,k\le |C|\le 300$

分析：

每个$S$中的点在路径$P$上第一次被访问的顺序为：
$v_0,v_1,v_2\dots \dots v_{|S|?1}$

性质1：

显然，路径$P$的起点必为$v_0$，终点必为$v_{|S|?1}$
并且，$P$是由$(v_0?>v_1),(v_1?>v_2),(v_3?>v_4)\dots \dots (v_{|S|?2}?>v_{|S|?1})$组成。其中$(u?>v)$表示从u到v的最短路径。
证明：因为是第一次出现的顺序，所以若不是最短路径，则最短路径一定更优。

性质2：

对于任意一条边$e$，其出现在$P$中的充要条件为：$e$分开的两个联通块中，均有点$x\in S$
证明略。

性质3：

对于任意一条边$e\in P$，其最多出现2次。
证明略。

性质4：

对于任意一条边$e\in P$，其出现一次的充要条件为：$e\in (v_0?>v_{|S|?1})$。
证明：如果把这条路径连上，则形成了一条回路，回路中每条边都一定访问2次。由性质1可得，这条回路从$v_{|S|?1}$回到$v_0$的过程中，一定走的是最短路。现在把这条$(v_{|S|?1}?>v_0)$路径删去，这条路径上的边就只走了一次。

现在，有了这么一堆性质，很容易发现：对于一个固定的$S$（随机出来的大小为k的$C$的子集），其最短路径$P$的长度为：$$2\times |E_s|?path(a?>b)$$
其中$E_s$是一定存在于路径$P$上的边的集合（即满足性质2的边的集合）。
$path(a?>b)$是从$a$到$b$的最短路。

$|E_s|$是固定的，因此要使得$path(a?>b)$尽可能大，即$(a,b)$为$S$中的最远点对。

根据期望的性质，对于这两个部分，可以分开考虑其期望贡献。（即分别算出$E(|E_s|)$和$E(path(a?>b))$）

计算$E(|E_s|)$

显然要考虑算每条边的贡献。

$E(|E_s|)=\sum p_e?1.0$（$p_e$是$e\in E_s$的概率）

考虑$e$两侧的联通块$A$,$B$

显然$p(e?\in E_s)=\frac{\left({}_{|C|}^{|A|}\right)+\left({}_{|C|}^{|B|}\right)}{\left({}_{|C|}^{|S|}\right)}$

那么$p(e\in E_s)=1?\frac{\left({}_{|C|}^{|A|}\right)+\left({}_{|C|}^{|B|}\right)}{\left({}_{|C|}^{|S|}\right)}$

所以，可以通过计算$e$两侧被选中点的个数，计算$e$出现在$E_s$中的概率，

具体方法可以利用树形DP，计算组合数复杂度为$O(K)$。这部分总复杂度控制在$O(NK)$左右即可。

计算$E(path(a?>b))$

显然，如果$path(a?>b)$有贡献，那么$path(a?>b)$必然是$E_s$所构成的子树的直径。

根据直径的经典性质：(a->b)是直径的充要条件为$?v\in S，满足len(v,a)<len(a,b),len(v,b)<len(a,b)$

利用这个性质，我们可以直接枚举所有满足这个条件的点集$F（F?C）$

$E(path(a?>b))=len(a,b)?\frac{\left({}_{|F|}^{|S|}\right)}{\left({}_{|C|}^{|S|}\right)}$

可以用N次bfs，预处理出来每两点之间的最短距离，然后枚举的复杂度是$O(|C{|}^3)$，可以接受。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#include<string>
#define SF scanf
#define PF printf
#define MAXN 2510
#define MAXC 310
using namespace std;
vector<string> s;
int n,m,tot,sum,totC,K;
vector<int> C;
vector<int> a[MAXN];
int dist[MAXC][MAXC];
int w[6][4]={
    {
    0,1},{
    1,0}};
double count(int x,int y){
    double ans=1;for(int i=0;i<K;i++)ans=ans*1.0*(x-i)/(1.0*(y-i));return ans;
}
pair<int,int> l[MAXN];
bool vis[MAXN];
int id[MAXN];
int dfs(int x,int fa){
    int res=(id[x]>0);for(int i=0;i<int(a[x].size());i++){
    int u=a[x][i];if(u==fa)continue;res+=dfs(u,x);	}return res;
}
double solve_edge(){
    double res=0;for(int i=1;i<=m;i++){
    int x=l[i].first;int y=l[i].second;int s1=dfs(x,y);int s2=totC-s1;	res+=1.0;if(s1>=K)res-=count(s1,totC);if(s2>=K)res-=count(s2,totC);}
}
bool bigger(int x,int y,int i,int j){
    if(i>j)swap(i,j);if(dist[x][y]!=dist[i][j])return dist[x][y]>dist[i][j];if(x!=i)return x>i;return y>j;	
}
double solve_road(){
    double res=0;for(int i=1;i<=totC;i++)for(int j=i+1;j<=totC;j++){
    int len=dist[i][j];int F=0;for(int k=1;k<=n;k++)if(k!=i&&k!=j&&bigger(i,j,k,i)&&bigger(i,j,k,j))F++;if(F>=K-2)res+=double(len)*count(F+2,totC)*double(K*(K-1))/double((F+2)*(F+1));PF("{%lf}\n",res);}return res;
}
void add_edge(int x,int y){
    l[++sum]=make_pair(x,y);a[x].push_back(y);a[y].push_back(x);
}
void dfs(int x,int rt,int len){
    vis[x]=1;if(id[x]!=0)dist[rt][id[x]]=len;for(int i=0;i<int(a[x].size());i++)if(vis[a[x][i]]==0)dfs(a[x][i],rt,len+1);
}
int main(){
    SF("%d%d",&n,&m);s.resize(n);for(int i=0;i<n;i++)cin>>s[i];SF("%d",&K);for(int i=0;i<n;i++)for(int j=0;j<m;j++){
    if(s[i][j]!='#')tot++;elsecontinue;if(s[i][j]=='*'){
    C.push_back(i*m+j+1);id[i*m+j+1]=C.size();}for(int k=0;k<2;k++){
    int i1=i+w[k][0];int j1=j+w[k][1];if(i1>=0&&j1>=0&&i1<n&&j1<m&&s[i1][j1]!='#')add_edge(i*m+j+1,i1*m+j1+1);}}totC=C.size();memset(dist,0x3f,sizeof dist);for(int i=0;i<totC;i++){
    memset(vis,0,sizeof vis);dfs(C[i],i+1,0);}for(int k=1;k<=totC;k++)for(int i=1;i<=totC;i++)for(int j=1;j<=totC;j++)dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);n=tot;m=sum;double x=solve_edge();double y=solve_road();PF("%lf",2.0*x-y);
}