一些 $\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)$ 时
对于离散变量 $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}$ 作为子序列/连续子序列的概率
$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$ 的个数
且有 $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
下的题
$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 ; }
$n$ 张卡牌,第 $i$ 张发动技能的概率为 $p_i$ ,若成功发动会造成 $d_i$ 点伤害,一局游戏有 $r$ 轮,每一轮中,从第一张开始按照顺序出牌:若当前第 $i$ 牌已成功发动过则跳过,若是最后一张则结束该;否则以 $p_i$ 的概率发动,若成功则结束该轮,否则考虑下一张
题中的 $p_i$ 并不能直接推出答案,考虑设 $fp_i$ 表示牌 $i$ 在所有的 $r$ 轮中被使用的概率,如此有答案 $\sum fp_i\times d_i$
显然需要一个 $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];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]); f[i][j]+=f[i-1 ][j]*(pow_j[i][r-j]); if (j) f[i][j]+=f[i-1 ][j-1 ]*(1 -pow_j[i][r-j+1 ]); } 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 (); }
一个树形结构,每个点有 $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 ;} 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 ; }
给定一个 $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 ; }
有两种操作:对于指定的 $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 ]; ll g[N]; ll h[N]; 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; } 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 () { 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 (" " ); } getchar (),getchar (); return 0 ; }
给出 $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]){ 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 ; }
$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 (!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); } } 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 ; }
给无向图,从节点 $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];double ans[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) { 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){ 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 ; }