概率与期望

一些 $\text{trick}$

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

总结

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

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

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

技巧/套路

由等比数列求和得：

$$\sum_{i=0}^n x^i=\frac{1-x^{n+1}}{1-x}$$

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

$$\sum_{i=0}^{\infty} x^i=\frac{1}{1-x}$$

• 期望的性质

  线性性： $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$ 的期望

$$\begin{aligned} E(\max)&=\sum_{i=1}^S P(\max=i)\times i \\ &=\sum_{i=1}^S \left(P(\max\leq i)-P(\max\leq i-1)\right)\times i \\ &=\sum_{i=1}^S \left(\frac{i^n}{S^n}-\frac{(i-1)^n}{S^n} \right)\times i \end{aligned}$$

拿球问题

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

$$\sum_{i=1}^n P(i)\times i=\sum_{i=1}^n \frac{m}{n}\times i=\frac{m(n+1)}{2}$$

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

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

感性理解一下，答案不变

游走问题

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

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

$$E(X_2)=\frac{1}{2}+\frac{1}{2}\times (1+E(X_1)+E(X_2))$$ $$E(X_i)=\frac{1}{2}+\frac{1}{2}\times (1+E(X_{i-1})+E(X_i))=E(X_{i-1})+2$$ $$E(ans)=\sum_{i=1}^{n-1}E(X_i)=(n-1)^2$$

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

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

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

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

$$\begin{cases} E_b=\frac{1}{n}+\frac{n-1}{n}(E_b+2) &\text{前者是到另一侧的期望步数，后者是另一侧又到另一侧的步数，系数表示不需要自己走回自己}\\ E_b=E_a+1 \\ \end{cases}$$

解得

$$\begin{cases} E_b=n+1 \\ E_a=n \\ \end{cases}$$

模型

每次随机一个整数 $[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$ ，所以平方无意义

$$\left(\sum_{i=1}^n X_i\right)^2=\sum_{i,j,i<j}^n \left(X_i\times X_j+X_i^2\right)$$ $$原式=\sum_{i,j,i<j}^n\left(E(X_i\times X_j+X_i)\right)=\sum_{i=1}^n E(X_i)+\sum_{i,j,i<j}^n E(X_i\times X_j)$$

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

$$原式=\sum_{i=1}^n \frac{1}{n}+\sum_{i=1,j>i}\frac{1}{i\times j}$$

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

• 第一问

  $$\binom{n}{m}\times \frac{(n-m)!}{n!}=\frac{1}{m!}$$

• 第二问

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

  $$\prod_{i=n-m+1}^n\frac{1}{i}=\frac{(n-m)!}{n!}$$

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

  $$ans=\frac{(n-m)!}{n!}\times (n-m+1)=\frac{(n-m+1)!}{n!}$$

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

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

$$\begin{aligned} E(X_1)&=\sum_{i=2}^n E([E_x\leq E_1])+1 \\ &=\sum_{i=2}^n P([E_x\leq E_1])+1 \\ &=\left(\sum_{i=1}^n \frac{a_i}{a_1-a_i}\right)+1 \\ \end{aligned}$$

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

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

• $S_{i+1}=0$

  $$Y_{i+1}=0,X_{i+1}=X_i$$

• $S_{i+1}=1$

  $$Y_{i+1}=Y_i+1,X_{i+1}=X_i-Y_i^2+(Y_i+1)^2=X_i+2\times Y_i+1$$

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

那么有

$$E(X_n)=p\times (\ E(X_{n-1})+2\times E(Y_{n-1}+1)\ )+(1-p)\times E(x_{n-1})$$ $$E(Y_n)=p\times (1+E(Y_{n-1}))+(1-p)\times 0$$

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

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

$$P=\frac{2\times (j-i-1)!}{(j-i+1)!}=\frac{2}{(j-i)(j-i+1)}$$

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

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

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

$$E(ans)=\sum_{i=1}^n E(X_i)=\sum_{i=1}^n\frac{1}{\left\lfloor\frac{i}{n} \right\rfloor}$$

即，$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$

由期望的线性性可知

$$E(S)=\sum_{i,j,i<j}^n E(x_{i,j})\times w_i\times w_j=\sum_{i,j,i<j}^n \frac{2\times w_i\times w_j}{(j-i)\times (j-i+1)}$$

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

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

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

$$E(S)=\sum_{i=1}^n E(X_i)\times a_i$$

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

那么有：

$$E(S)=\sum_{i=1}^n\sum_{j=1}^{n-1}\frac{2\times a_i}{n-j+1}$$

刷一波期望 tag 下的题

P3232 [HNOI2013]游走

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

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

$$f_i=\begin{cases} \sum_{i,j\in E,j!=n} \frac{f_j}{deg_j}+1 &\text{ $i=1$ } \\ \sum_{i,j\in E,j!=n} \frac{f_j}{deg_j} \\ 0 &\text{ $i=n$ } \\ \text{注意这里面是 $deg_j$ 而不是 $deg_i$ } \\ \end{cases}$$

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

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

直接排序求即可

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$ 张发动的概率，则有

$$f_{i,j}+= \begin{cases} (1-(1-p_i)^{r-j+1})\times f_{i-1,j-1} &\text{$i$ 发动，此时有 $j-1$ 轮不能发动} \\ (1-p_i)^{r-j}\times f_{i-1,j} &\text{$i$ 不发动，那么有 $j$ 轮不能发动} \\ \end{cases}$$

那么易得 $fp$ :

$$fp_i=\sum_{j=0}^{min(i-1,j)} (1-(1-p_i)^{r-j})\times f_{i-1,j}$$

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}$ 的概率给其他点间接充电，求进入充电状态的点的个数期望

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

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

$$\begin{cases} &\text{自身以 $q_i$ 的概率充电} \\ &\text{被其 $son$ 充电} \\ &\text{被其 $fa$ 充电} \\ \end{cases}$$

树形图容易考虑到一个 $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}$

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]$ 中等概率选取两点之间的期望距离

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

$$ans=\frac{\sum_{i=l}^r\sum_{j=i}^r (pre_j-pre_i)}{\binom{r-l+1}{2}}$$

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

一个 $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)$

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

$$\begin{aligned} 分子&=\sum_{i=l}^r a_i\times (r-i+1)\times (i-l+1) \\ &=-\sum_{i=l}^r a_i\times i^2+\sum_{i=l}^r a_i\times i\times (r-l)+\sum_{i=l}^r a_i\times (r-l+1-lr) &\text{拆开并化简得} \\ \end{aligned}$$

这样就能用线段树维护了，具体的，分别用 $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$

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$ ，即，

$$\begin{cases} f_{i,j}=p\times f_{i,j+1}+(1-p)\times f_{i,j} \\ 特殊的,f_{i,0}=p\times f_{i,j+1}+f_{i,j} \\ \end{cases}$$

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

$$g_j=alive_u\times h_{u,j-1}+dead_u\times h_{u,j}$$ $$h_{u,j}=\frac{g_j-alive_u\times h_{u,j-1}}{dead_u}$$

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

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$ 所经过的节点数的期望值，那么有：

$$dp_u=\frac{1}{deg_u}\left(\sum_{u,v\in E}dp_v\right)+1$$

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

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

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

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

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

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$ 的平均步数

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$ 的步数异或和的期望，那么有：

$$ans_u=\frac{1}{out_u} \left(\sum_{at \ edge_{rk},edge_{u,v}=0}f_v \ + \ \sum_{at\ edge_{rk},edge_{u,v}=1} (1-f_v) \right)$$

由异或性质易得

为了便于高斯消元有：

$$ans_u \times out_u=\left(\sum_{at \ edge_{rk},edge_{u,v}=0}f_v \ + \ \sum_{at\ edge_{rk},edge_{u,v}=1} (1-f_v) \right)$$

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

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;
}