0%

概率与期望

一些 $\text{trick}$

定义 $E(x)$ 表示随机变量 $x$ 的期望值,即,$E(x)=\sum P(x=i)\times i$

总结

先定义目标状态的期望 $E(S)$

用期望的线性性拆成若杠 $\sum E(x_{0,1,2,….})$ 并分类

对于每一类找递推式或直接算的式子,或考虑引入新的值来辅助计算

技巧/套路

由等比数列求和得:

$n\rightarrow \infty,x\in (0,1)$ 时

  • 期望的性质

    线性性: $E(x+y)=E(x)+E(y)$

    不相关可积性: $E(xy)=E(x)\times E(y)$

对于离散变量 $x$ :$P(x=k)=P(x\leq k)-P(x\leq k-1)$

例子

$n$ 个随机变量 $x_i,\forall x_i,1\leq x_i\leq S$ ,求 $\max_{1\leq i\leq n} x_i$ 的期望

拿球问题

$n$ 个球,拿 $m$ 次,求拿出的数字之和期望

其中是否放回对答案无影响

拿出求后有 $p_1$ 的概率放回,$p_2$ 的概率放回两个和该球相同的,求期望

感性理解一下,答案不变

游走问题

链上从一段到另一端的期望步数

设 $X_i$ 表示 随机游走下 $i$ 第一次到 $i+1$ 的步数

完全图上,从一个点到另一个点的期望

$\frac{1}{n-1}$ 成功,则期望步数即为 $n-1$

$2n$ 点的完全二分图上游走

设 $E_a$ 表示在同侧的期望步数,$E_b$ 表示在异侧的期望步数,有:

解得

模型

每次随机一个整数 $[1,n]$ ,求凑齐所有数的期望次数

单次概率 $P=\frac{n-i+1}{n}$

期望即为 $E(x)=\sum_{i=1}^n\frac{1}{p_i}$

随机长度为 $n$ 的排列 $P$ ,求 $\max=P_i$ 的 $i$ 的个数的平方的期望和

设 $X_i$ 表示 $i$ 是否满足条件的期望

要求的为:$E\left(\left(\sum_{i}^n X_i\right)^2\right)$

若 $i$ 被选,$X_i$ 就是 $1$ ,否则为 $0$ ,所以平方无意义

由于 $X_i,X_j$ 相互独立,则有:

随机长度为 $n$ 的排列 $P$ ,求其包含 $w_{1\sim m}$ 作为子序列/连续子序列的概率

  • 第一问

  • 第二问

    取 $m$ 个位置,第一个位置 $n$ 种,第二个 $n-1$ 种,一直乘到 $n-m+1$ 种,在这 $m$ 个位置选出正确的 $w_i$ 的概率为

    再枚举开头,有 $n-m+1$ 种,即有

$n$ 堆石头,第 $i$ 堆有 $a_i$ 个,每次随机选一个石头并扔掉其所在堆的所有石头,求第 $1$ 堆石头期望第几次被扔掉

设 $X_i$ 表示 $i$ 是第 $X_i$ 次被拿走,即有 $X_i=\sum_{i-1}^m [X_i\leq X_1]$

随机长度 $n$ 的 $01$ 串 $S$ ,每个位置为 $1$ 的概率为 $p$ ,定义 $ans$ 是每段连续 $1$ 长度的平方之和,求 $E(ans)$

定义 $X_i$ 表示以 $i$ 结尾时1的答案,$Y_i$ 表示以 $i$ 结尾时后缀 $1$ 的个数

  • $S_{i+1}=0$

  • $S_{i+1}=1$

且有 $E(X_n)=E(ans)$

那么有

给定序列,每次随机删除一个元素,求 $ij$ 在过程中相邻的概率

将 $ij$ 中间的数全排列,$ij$ 在最后的方案数除以总数

给定 $1\sim n$ 这 $n$ 个数,每次随机选择一个并删除其所有约数,求删完的期望

题意转化为随机删除 $x$ ,若其未被标记则标记其所有的约数,求期望选到多少个没被标记的 $x$

设 $X_i$ 表示 $i$ 在没被标记前就被删掉的期望

即,$i$ 的倍数有 $\left\lfloor\frac{i}{n} \right\rfloor$ 个, $i$ 最早被删除的概率即为 $\frac{1}{\left\lfloor\frac{i}{n} \right\rfloor}$

例题

给定 $n$ 个硬币,价值为 $val_i$ ,每次随机取走一个,获得的收益时左右两个硬币价值的乘积,求总期望

设 $x_{i,j}=[ij是否相遇]$

那么总价值为 $S=\sum_{i,j} x_{i,j}\times w_i\times w_j$

由期望的线性性可知

$n$ 个数 $a_{1\sim n}$ 每次等概率选出两个数,合并在一起为一个新数并放回,得到的收益时新的数的值,求总收益期望

设 $X_i$ 表示 $a_i$ 被选的次数

总收益即为 $S=\sum_{i=1}^n X_i\times a_i$

一个数 $a_x$ 在第 $j$ 次被合并的概率和是 $\sum_{j=1}^{n-1}\frac{2}{n-j+1}$ ,即,每个数独立,第 $j$ 次还剩 $n-j+1$ 个数

那么有:

刷一波期望 tag 下的题

P3232 [HNOI2013]游走

$n$ 个点 $m$ 个边的无向连通图,在该图上随机游走,每一步中以相等概率随机选择当前点的某条边,沿该边走后获得该边编号的分数,到 $n$ 时游走结束,对 $m$ 条边编号使总分的期望值最小

由数据范围 $1\leq n\leq 500,1\leq m\leq 125000$ 可以考虑到:若直接考虑边的期望经过次数时间复杂度不能接受,所以先考虑点的期望经过次数,即:

对于这 $n-1$ 个式子(没有 $n$ ) ,用高斯消元求解易得

那么边的期望经过次数即为 $g(u,v)=\frac{f_u}{deg_u}+\frac{f_v}{deg_v}$

直接排序求即可

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
const int N=550,M=2e5+100;
const double eps=1e-10;
int head[M],ver[M<<1],Next[M<<1],tot;
int n,m,s[M<<1],ed[M<<1];
double d[N],f[N][N],ans[N],sum,E[M<<1];

inline void add(int u,int v){ ver[++tot]=v; Next[tot]=head[u];head[u]=tot;}
inline int dcmp(double x){ return (x<=eps && x>=-eps) ? 0 : (x>0 ? 1 : -1);}

inline void gauss(){
for(rei i=1;i<n;++i){
rei num=i;
for(rei j=i+1;j<n;++j) if(dcmp(f[j][i]-f[num][i])>0) num=j;
if(num!=i) for(rei j=1;j<=n;++j) swap(f[i][j],f[num][j]);
for(rei j=i+1;j<n;++j) if(dcmp(f[j][i])){
double t=f[j][i]/f[i][i];
for(rei k=1;k<=n;++k) f[j][k]-=t*f[i][k];
}
}
for(rei i=n-1;i;--i){
for(rei j=i+1;j<n;++j) f[i][n]-=f[i][j]*ans[j];
ans[i]=f[i][n]/f[i][i];
}
}

int main(){
freopen("1.in","r",stdin); freopen("1.ans","w",stdout);
scanf("%d%d",&n,&m);
for(rei i=1,x,y;i<=m;++i) scanf("%d%d",&x,&y),add(x,y),add(y,x),++d[x],++d[y],s[i]=x,ed[i]=y;
for(rei i=1;i<n;++i){
f[i][i]=1.0;
for(rei j=head[i];j;j=Next[j]){
rei y=ver[j]; if(y==n) continue;
f[i][y]=-1/d[y];
}
}
f[1][n]=1;
gauss();
for(rei i=1;i<=m;++i) E[i]=ans[ s[i] ]/d[ s[i] ]+ans[ ed[i] ]/d[ ed[i] ];
sort(E+1,E+1+m);
for(rei i=1;i<=m;++i) sum+=E[i]*(m-i+1.0);
printf("%.3lf\n",sum);
getchar(),getchar();
return 0;
}

P3239 [HNOI2015]亚瑟王

$n$ 张卡牌,第 $i$ 张发动技能的概率为 $p_i$ ,若成功发动会造成 $d_i$ 点伤害,一局游戏有 $r$ 轮,每一轮中,从第一张开始按照顺序出牌:若当前第 $i$ 牌已成功发动过则跳过,若是最后一张则结束该;否则以 $p_i$ 的概率发动,若成功则结束该轮,否则考虑下一张

题中的 $p_i$ 并不能直接推出答案,考虑设 $fp_i$ 表示牌 $i$ 在所有的 $r$ 轮中被使用的概率,如此有答案 $\sum fp_i\times d_i$

  • 对于 $fp_i$

    显然有 $fp_1=1-(1-p_1)^r$

    考虑第 $2$ 张牌,若第 $1$ 张牌发动则有 $fp_2=1-(1-p_2)^{r-1}$ ,若没有发动则有 $fp_2=1-(1-p_2)^r$

    那么有结论:若已经确定 $\forall i>1$ 在 $1\sim i-1$ 张牌在所有 $r$ 轮种是否发动技能,$fp_i$ 仅取决于 $1\sim i-1$ 有多少张发动的牌,即 $fp_i=1-(1-p_i)^{r-j}$

显然需要一个 $dp$ 来维护,即 $f_{i,j}$ 表示 $r$ 轮中前 $i$ 张牌中有 $j$ 张发动的概率,则有

那么易得 $fp$ :

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
const int N=250,M=150;
int n,r,d[N];
double p[N],fp[N],pow_j[N][N];//pow_j[i][j]: (1-p[i])^j
double f[N][M];

inline void init(){
for(rei i=0;i<n;++i){
pow_j[i][0]=1;
for(rei j=1;j<=r;++j) pow_j[i][j]=pow_j[i][j-1]*(1-p[i]);
}
}

inline double solve(){
memset(f,0,sizeof f); memset(fp,0,sizeof fp);
f[0][0]=pow_j[0][r]; f[0][1]=fp[0]=1-f[0][0];
for(rei i=1;i<n;++i) for(rei j=0;j<=r;++j){
fp[i]+=f[i-1][j]*(1-pow_j[i][r-j]);//对于前i-1张,j轮不考虑第i张,r-j轮考虑
f[i][j]+=f[i-1][j]*(pow_j[i][r-j]);//不选第i张
if(j) f[i][j]+=f[i-1][j-1]*(1-pow_j[i][r-j+1]);//选第i张
}
double res=0;
for(rei i=0;i<n;++i) res+=d[i]*fp[i];
return res;
}

int main(){
rei T; scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&r);
for(rei i=0;i<n;++i) scanf("%lf%d",&p[i],&d[i]);
init();
printf("%.10lf\n",solve());
}
getchar(),getchar();
}

P4284 [SHOI2014]概率充电器

一个树形结构,每个点有 $p_i$ 的概率直接被充电,随后直接充电的点以 $edge_{i,j}$ 的概率给其他点间接充电,求进入充电状态的点的个数期望

注意:被间接充电的点也可以给其他点充电

先考虑一个点有电的情况:

树形图容易考虑到一个 $trick$ : $\text{up \ and \ down}$ :先从下往上推得前两种情况,再从根往下推第三种

具体的,设每个点的初始概率即为 $q_i\%$

  • 对于 $up$ 操作:

    设事件 $A$ 表示点 $i$ 直接充电,事件 $B$ 表示点 $i$ 被子节点间接充电,那么至少发生一件的概率为 $P(A)+P(B)-P(A)\times P(B)$

    即,$h_i=h_i+h_j\times edge_{i,j}-h_i\times h_j\times edge_{i,j},\quad j\in son_i$

  • 对于 $down$ 操作:

    即,用父亲有电来更新儿子

    设事件 $A$ 表示除了子树 $j$ 以外的使 $i$ 有电的概率,又有 $P(B)=h_j\times edge_{i,j}$

    那么有 $P(A)=\frac{h_i-P(B)}{1-P(B)}$ , $h_j=h_j+P(A)\times edge_{i,j}-h_j\times P(A)\times edge_{i,j}$

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
const int N=5e5+100;
const double eps=1e-10;
int n,m;
int head[N],Next[N<<1],ver[N<<1],val[N<<1],tot;
int a[N],depth[N];
double h[N],ans;

inline void add(int u,int v,int z){ ver[++tot]=v; Next[tot]=head[u],head[u]=tot,val[tot]=z;}
inline int check(double x,double y){ return (x+eps>y && x-eps<y) ? 1 : 0;}

void up(int x){
for(rei i=head[x];i;i=Next[i]){
rei y=ver[i]; if(depth[y]) continue;
depth[y]=depth[x]+1;
up(y);
double P2=h[y]*(double) val[i]/100;
h[x]=h[x]+P2-h[x]*P2;
}
}

void down(int x){
ans+=h[x];
for(rei i=head[x];i;i=Next[i]){
rei y=ver[i]; if(depth[y]<=depth[x]) continue;
if(check(h[y]*(double) val[i]/100,1)){ down(y); continue;}//h_j已经是1,不需要再更新
double P2=(h[x]-h[y]*(double) val[i]/100)/(1-h[y]*(double) val[i]/100);
P2*=(double) val[i]/100;
h[y]=h[y]+P2-P2*h[y];
down(y);
}
}

int main(){
scanf("%d",&n);
for(rei i=1,x,y,z;i<n;++i) scanf("%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);
for(rei i=1;i<=n;++i) scanf("%d",&a[i]),h[i]=a[i]*0.01;
depth[1]=1;
up(1); down(1);
printf("%.6lf\n",ans);
getchar(),getchar();
return 0;
}

P2221 [HAOI2012]高速公路

给定一个 $1\sim n$ 区间,要求区间加,并求出 $[l,r]$ 中等概率选取两点之间的期望距离

显然需要用线段树来维护一些东西,考虑答案的形式:

考虑如何用线段树维护分子:

一个 $trick$ 是枚举 $[l,r]$ 中每一个位置被包含多少次:

$l$ :被 $[l,l],[l,l+1],…$ 等 $r-l+1$ 个包含

$l+1$ :被 $[l+1,l+1],[l+1,l+2],…[l,l+1],[l,l+2],…$ 等 $2(r-l)$ 个包含

$l+i$ :以 $l+i$ 开头的包含 $r-i+1$ 次 $\cup$ 以 $l+i-1$ 开头的包含 $r-i+1$ 次 $\cup…\cup$ 以 $l$ 开头的 包含$r-i+1$ 次 $\Leftrightarrow$ $(r-i+1)(i-l+1)$

此时需要维护的分子转化为:

这样就能用线段树维护了,具体的,分别用 $ai_0,ai_1,ai_2$ 维护 $\sum a_i,\sum a_i\times i,\sum a_i\times i^2$

对于区间修改,不难想到再额外维护 $sumi_1,sumi_2$ 表示 $\sum i,\sum i^2$

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
const int N=1e5+100;
int n,m;

namespace SGT{
struct node{
ll ai_0,ai_1,ai_2,sum_i,sum_i2;
ll lazy;
}tr[N<<2];
inline void pushup(int now){
tr[now].ai_0=tr[now<<1].ai_0+tr[now<<1|1].ai_0;
tr[now].ai_1=tr[now<<1].ai_1+tr[now<<1|1].ai_1;
tr[now].ai_2=tr[now<<1].ai_2+tr[now<<1|1].ai_2;
}
inline void pushdown(int now,int l,int r){
if(tr[now].lazy){
rei mid=l+r>>1,w=tr[now].lazy;
tr[now<<1].lazy+=(ll) w,tr[now<<1|1].lazy+=(ll) w;
tr[now<<1].ai_0+=(ll) (mid-l+1)*w,tr[now<<1|1].ai_0+=(ll) (r-mid)*w;
tr[now<<1].ai_1+=(ll) w*tr[now<<1].sum_i,tr[now<<1|1].ai_1+=(ll) w*tr[now<<1|1].sum_i;
tr[now<<1].ai_2+=(ll) w*tr[now<<1].sum_i2,tr[now<<1|1].ai_2+=(ll) w*tr[now<<1|1].sum_i2;
tr[now].lazy=0;
}
}
void build(int now,int l,int r){
if(l==r) return tr[now].sum_i=l,tr[now].sum_i2=(ll) l*l,void();
rei mid=l+r>>1;
build(now<<1,l,mid),build(now<<1|1,mid+1,r);
tr[now].sum_i=tr[now<<1].sum_i+tr[now<<1|1].sum_i;
tr[now].sum_i2=tr[now<<1].sum_i2+tr[now<<1|1].sum_i2;
}
void update(int now,int l,int r,int L,int R,ll w){
if(l>R || r<L) return;
if(l>=L && r<=R){
tr[now].ai_0+=(ll) (r-l+1)*w;tr[now].ai_1+=(ll) w*tr[now].sum_i;
tr[now].ai_2+=(ll) w*tr[now].sum_i2;tr[now].lazy+=w;return;
}
pushdown(now,l,r);
rei mid=l+r>>1;
update(now<<1,l,mid,L,R,w),update(now<<1|1,mid+1,r,L,R,w);
pushup(now);
}
void query(int now,int l,int r,int L,int R,ll &ai_0,ll &ai_1,ll &ai_2){
if(l>R || r<L) return;
if(l>=L && r<=R) return ai_0+=tr[now].ai_0,ai_1+=tr[now].ai_1,ai_2+=tr[now].ai_2,void();
pushdown(now,l,r);
rei mid=l+r>>1;
query(now<<1,l,mid,L,R,ai_0,ai_1,ai_2);
query(now<<1|1,mid+1,r,L,R,ai_0,ai_1,ai_2);
}
}

int main(){
scanf("%d%d",&n,&m);
SGT::build(1,1,n);
while(m--){
char s[2]; ll l,r; scanf("%s%lld%lld",s,&l,&r);
if(s[0]=='C'){
ll w; scanf("%lld",&w);
if(l==r) continue;
SGT::update(1,1,n,l+1,r,w);
}else{
ll S1=0,S2=0,S3=0;
SGT::query(1,1,n,l+1,r,S1,S2,S3);
ll son=-S3+(l+r+1)*S2+(r-(l+1)-(l+1)*r+1)*S1,mo=(r-l+1)*(r-l)/2;
ll gcd=__gcd(son,mo);
printf("%lld/%lld\n",son/gcd,mo/gcd);//约分
}
}
getchar(),getchar();
return 0;
}

P4564 [CTSC2018]假面

有两种操作:对于指定的 $id$ ,有 $p$ 的概率对 $id$ 造成 $1$ 点伤害;针对 $k$ 个指定单位并恰好命中一个,命中每个存活的单位的概率相等,若 $k$ 个单位均死亡则不会命中任何地方单位

对于操作 $2$ ,求其命中各敌人的概率分别是多少;所有操作进行完后,所有单位的剩余生命值的期望

首先两个操作之间是互相独立的

先考虑第 $i$ 个人的剩余生命值期望:$E(i)=\sum_{j=0}^{a_i} j\times f_{i,j}$ ,其中 $f_{i,j}$ 表示第 $i$ 个人的剩余生命值为 $j$ 的期望

每次操作 $1$ 进行后能以 $O(a_i)$ 的复杂度维护 $f_i$ ,即,

设 $g_j$ 表示 $j$ 人存活的概率,$h_{u,j}$ 表示除了 $u$ 还有 $j$ 人存活,那么有:

可以做到 $O(n^2)$ 预处理并 $O(1)$ 查询

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
const int N=210;
const int mod=998244353;
ll inv[N],a[N],b[N];
ll f[N][105];//第i个人有j点生命的概率
ll g[N];//g_j:j个人活着的概率
ll h[N];//h_{u,j} 除了u还有j个人
int n,Q;

inline int qpow(ll x,int y,ll res=1){ while(y){ if(y&1) res=res*x%mod; y>>=1; x=x*x%mod;}; return res;}

inline void attack(int i,ll p){
ll q=(1-p+mod)%mod;//不命中
for(rei j=0;j<=a[i];++j) j ? f[i][j]=(p*f[i][j+1]%mod+q*f[i][j]%mod)%mod : f[i][j]=(p*f[i][j+1]%mod+f[i][j])%mod;//特殊的,j=0时其系数q不重要
}

inline void solve(int k){
memset(g,0,sizeof g); g[0]=1;
for(rei i=1;i<=k;++i){
ll alive=(mod+1ll-f[ b[i] ][0])%mod;
ll dead=(mod+1ll-alive)%mod;
for(rei j=i;j>=0;--j) j ? g[j]=(g[j]*dead+g[j-1]*alive%mod)%mod : g[j]=g[j]*dead%mod;
}
for(rei u=1;u<=k;++u){
ll ans=0;
ll alive=(mod+1ll-f[ b[u] ][0])%mod,dead=(mod+1ll-alive)%mod;
memset(h,0,sizeof h);
if(alive!=1){
ll invd=qpow(dead,mod-2);
h[0]=g[0]*invd%mod;
for(rei j=1;j<k;++j) h[j]=(g[j]-alive*h[j-1]%mod+mod)%mod*invd%mod;
}
else for(rei j=0;j<=k;++j) h[j]=g[j+1];
for(rei j=0;j<k;++j) ans=(ans+h[j]*inv[j+1]%mod)%mod;
ans=ans*alive%mod;
printf("%d ",ans);
}
puts("");
}

int main(){
// freopen("1.in","r",stdin); freopen("1.out","w",stdout);
scanf("%d",&n);
for(rei i=1;i<=n;++i){
scanf("%d",&a[i]);
inv[i]=qpow(i,mod-2);
f[i][ a[i] ]=1;
}
scanf("%d",&Q);
while(Q--){
rei op; scanf("%d",&op);
if(!op){
int id; ll u,v; scanf("%d%lld%lld",&id,&u,&v);
attack(id,(ll) u*qpow(v,mod-2)%mod);
}
else{
rei k; scanf("%d",&k);
for(rei i=1;i<=k;++i) scanf("%d",&b[i]);
solve(k);
}
}
for(rei i=1;i<=n;++i){
ll ans=0;
for(rei j=1;j<=a[i];++j) ans=(ans+(ll) j*f[i][j]%mod)%mod;
printf("%d",ans); if(i!=n) printf(" ");
}
// puts("");
getchar(),getchar();
return 0;
}

P6030 [SDOI2012]走迷宫

给出 $n$ 点 $m$ 边的有向图,有起点 $s$ ,终点 $t$ ,从一个点随机沿一条有向边到另一个点,求到终点的步数期望值

显然有 $dp_u$ 表示节点 $u$ 走到节点 $n$ 所经过的节点数的期望值,那么有:

由于有环的情况,需要高斯消元,但数据范围并不允许这么做

重新审视题中条件:每个强连通分量大小 $\leq 100$ ,那么可以用 $tarjan-scc$ 缩点,缩点后即为一个 $DAG$

显然需要倒序计算 $dp$ 值以保证所需的值要么是未知数要么是已经被计算出来的(看作常数)

那么,从 $s$ 开始做缩点所得的强连通分量的编号就是以 $t$ 为起点在 $DAG$ 上做的拓扑所得的拓扑序

那么直接从 $1\sim 强连通分量个数$ 依次在当前强连通分量中做高斯消元即可

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
const int S=110,N=1e4+10,M=1e6;
const double INF=1e15;
int n,m,s,t;
int head[N],ver[M<<1],Next[M<<1],tot;
int bel[N],cnt,dfn[N],low[N],dfn_cnt,stk[N],top;
bool vis[N];
int id[N],seq[S],subsiz,deg[N];
double dp[N],a[S][S],f[S];
vector<int> scc[N],rev[N];
bool can[N];

inline void add(int u,int v){ ver[++tot]=v,Next[tot]=head[u],head[u]=tot;}

void dfs(int x){
if(can[x]) return ;
can[x]=1; for(int y:rev[x]) dfs(y);
}

inline void tarjan(int x){
dfn[x]=low[x]=++dfn_cnt; vis[x]=1; stk[++top]=x;
for(rei i=head[x];i;i=Next[i]){
rei y=ver[i];
if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);
else if(vis[y]) low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x]){
++cnt; rei y;
do{
y=stk[top--];vis[y]=0;
scc[ bel[y]=cnt ].push_back(y);
}while(y!=x);
}
}

int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for(rei i=1,u,v;i<=m;++i){
scanf("%d%d",&u,&v); ++deg[u]; add(u,v);
rev[v].push_back(u);
}
tarjan(s);
dfs(t);
if(!dfn[t]) return puts("INF"),0;
for(rei i=1;i<=cnt;++i){
subsiz=0;
memset(a,0,sizeof a),memset(f,0,sizeof f);
for(int u:scc[i]) seq[++subsiz]=u,id[u]=subsiz;
for(int u:scc[i]){//取出连通块 scc_i 内的点并放到代求里
rei p=id[u];
if(u==t){ a[p][p]=1; continue;}
a[p][p]=a[p][subsiz+1]=deg[u];
for(rei i=head[u];i;i=Next[i]){
rei v=ver[i];
if(bel[v]==bel[u]) --a[p][ id[v] ];
else a[p][subsiz+1]+=dp[v];
}
if(!can[u]) a[p][subsiz+1]=INF;
}
for(rei j=1;j<=subsiz;++j){//连通块内做高斯消元
rei t=j;
for(rei k=j+1;k<=subsiz;++k) if(fabs(a[k][j])>fabs(a[t][j])) t=k;
for(rei k=j;k<=subsiz+1;++k) swap(a[t][k],a[j][k]);
for(rei k=j+1;k<=subsiz+1;++k) a[j][k]/=a[j][j];
a[j][j]=1;
for(rei k=j+1;k<=subsiz;++k){
for(rei l=j+1;l<=subsiz+1;++l) a[k][l]-=a[k][j]*a[j][l];
a[k][j]=0;
}
}
for(rei j=subsiz;j;--j){
f[j]=a[j][subsiz+1];
for(rei k=j+1;k<=subsiz;++k) f[j]-=f[k]*a[j][k];
}
for(rei j=1;j<=subsiz;++j){
if(f[j]>1e9) dp[ seq[j] ]=INF;
else dp[ seq[j] ]=f[j];
}
}
dp[s]>1e9 ? puts("INF") : printf("%.3lf\n",dp[s]);
getchar(),getchar();
return 0;
}

P4206 [NOI2005] 聪聪与可可

$n$ 点 $m$ 边的有向图,$A$ 在点 $S$ ,$B$ 在点 $T$ ,$B$ 每次 等概率移动至相邻节点或不动,$A$ 每次可以移动 $1$ 步或 $2$ 步来追逐 $B$ ,$A$ 先走 $B$ 后走,求 $A$ 追到 $B$ 的平均步数

$A$ 的移动方案并不好实时处理,考虑预处理 $go_{i,j}$ 表示 $A$ 在 $i$ ,$B$ 在 $j$ 时,$A$ 下一步最优走到的位置,为此还需处理最短路 $dis_{i,j}$

直接记忆化搜索 $f_{s,t}$ 表示 $A$ 在 $s$ ,$B$ 在 $t$ 时,$A$ 追到 $B$ 的平均步数

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
const int N=1010;
const int INF=0x3f3f3f3f;
const double EPS=1e-8;
int go[N][N],dis[N][N],vis[N];
int head[N],ver[N<<1],Next[N<<1],tot;
int n,m,S,T;
double res[N][N],p[N];
queue<int> q;

inline void add(int u,int v){ ver[++tot]=v; Next[tot]=head[u],head[u]=tot;}
inline bool check(double x,int num){ return (x-EPS<=0.0 && x+EPS>=0.0) ? 1 : 0;}
inline void spfa(int *dis,int id){
dis[id]=0; q.push(id);
while(q.size()){
rei x=q.front(); q.pop(); vis[x]=0;
for(rei i=head[x];i;i=Next[i]){
rei y=ver[i];
if(dis[x]+1<dis[y]){
dis[y]=dis[x]+1;
if(!vis[y]) vis[y]=1,q.push(y);
}
}
}
}

double dfs(int s,int t){
// if(res[s][t]) return res[s][t];
if(!check(res[s][t],0)) return res[s][t];
if(s==t) return 0.0;
rei fi_st=go[s][t],se_st=go[fi_st][t];
if(fi_st==t || se_st==t) return 1.0;
res[s][t]=1.0;
for(rei i=head[t];i;i=Next[i]) res[s][t]+=dfs(se_st,ver[i])/(1+p[t]);
res[s][t]+=dfs(se_st,t)/(1+p[t]);
return res[s][t];
}

inline void init(){
memset(dis,INF,sizeof dis),memset(go,INF,sizeof go);
for(rei i=1;i<=n;++i) spfa(dis[i],i);
for(rei i=1;i<=n;++i) for(rei x=head[i];x;x=Next[x]){
rei y=ver[x];
for(rei j=1;j<=n;++j) if(dis[i][j]-1==dis[y][j]) go[i][j]=min(go[i][j],y);//注意取最小的编号
}
// for(rei i=1;i<=n;++i) for(rei j=1;j<=n;++j) printf("%d%c",go[i][j],j==n ? 10 : 32);
}

int main(){
scanf("%d%d%d%d",&n,&m,&S,&T);
for(rei i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),add(u,v),add(v,u),++p[u],++p[v];
init();
printf("%.3lf\n",dfs(S,T));
getchar(),getchar();
return 0;
}

P3211 [HNOI2011]XOR和路径

给无向图,从节点 $1$ 开始等概率走到下一个点,直至到 $n$ ,求路径 $xor和$ 的期望

一开始想偏到边的期望经过次数了

对于涉及位运算的题,先考虑是否能拆开一位一位的做

由期望的线性性可知拆开做的正确性

对于每一位 $rk$ : 设 $ans_i$ 表示点 $i$ 到点 $n$ 的步数异或和的期望,那么有:

由异或性质易得

为了便于高斯消元有:

复杂度 $O(30\times n^3)$

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
const int N=110,M=1e5+100;
const double EPS=1e-10;
double k[N][N];//edge_{u,v}=0/1 : -1/1 高斯消元系数
double ans[N];//i->n 的步数的第 [当前位] 的异或和的期望
int head[N],ver[M],Next[M],tot,val[M],out[N];
double res;
int n,m,MAX_rk;

inline void add(int u,int v,int z){ ver[++tot]=v; Next[tot]=head[u],head[u]=tot; val[tot]=z;}
inline bool check(double x){ return fabs(x)<EPS ? 0 : (x<0 ? -1 : 1);}
inline void get_k(int rk){//目前讨论第rk位
memset(k,0,sizeof k);
k[n][n]=1;
for(rei x=1;x<=n-1;++x){
k[x][x]=out[x];
for(rei i=head[x];i;i=Next[i]) (val[i]&rk) ? ++k[x][ ver[i] ],++k[x][n+1] : --k[x][ ver[i] ];
}
}

inline void gauss(){
for(rei i=1,MAX=i;i<=n;++i,MAX=i){
for(rei j=i;j<=n;++j) if(check(k[MAX][i]-k[j][i])) MAX=j;
for(rei j=i+1;j<=n;++j) if(check(k[j][i])){
double tmp=k[j][i]/k[i][i];
for(rei kk=i;kk<=n+1;++kk) k[j][kk]-=k[i][kk]*tmp;
}
}
for(rei i=n;i;--i){//这样就不需要清空ans了
for(rei j=i+1;j<=n;++j) k[i][n+1]-=k[i][j]*ans[j];
ans[i]=k[i][n+1]/k[i][i];
}
}

int main(){
scanf("%d%d",&n,&m);
for(rei i=1,u,v,w;i<=m;++i) scanf("%d%d%d",&u,&v,&w),MAX_rk=max(MAX_rk,w),add(u,v,w),++out[u],(u==v) ? 0 : (add(v,u,w),++out[v]);//要求异或和,两次异或不变,存自环无意义
for(rei i=1;i<=MAX_rk;i<<=1) get_k(i),gauss(),res+=1.0*i*ans[1];
printf("%.3Lf\n",res);
getchar(),getchar();
return 0;
}