首页 > 其他分享 >概率期望从入门到进门

概率期望从入门到进门

时间：2024-02-16 11:44:40浏览次数：27  
标签：mathbb frac 入门 int sum times 期望 进门

概率的线性性

  • 定义：\(\mathbb {E}(X)=\sum_i\times P(X=i)\)。

其中 \(x\) 为变量。

线性性

\[\begin{aligned}\mathbb{E}(aX+bY)&=\sum i\times P(aX+bY=i)\\&=\sum i\sum_j\sum_k[j+k=i]P(aX=j)P(bY=k)\\&=\sum_j\sum_k(j+k)P(aX=j)\cdot P(bY=k)\\&=\sum_jjP(aX=j)\sum_kP(bY=k)+\sum_kkP(bY=k)\sum_jP(aX=j)\\&=a\mathbb{E}(x)+b\mathbb{E}(y)\end{aligned} \]

容斥模型

前缀和

\[P(x=k)=P(x\leq k)- P(x\leq k-1) \]

  • 有 \(n\) 个随机变量 \(X_{1\sim n}\)，每个变量的值为 \(1\sim S\) 中的整数，则 \(\min\{X\}\) 的期望为 \(\sum_{i=1}^S(\frac{S-i+1}{S})^n\)。

随机游走

  • 假设一个点的度数为 \(k\)，那么它会随机走到任何一个出点上去，到达任意一个点的概率为 \(\frac{1}{k}\)。

链上随机游走

  • 在一个长度为 \(n\) 的链上随机游走，问 \(1\) 走到 \(n\) 的期望步数。

根据期望的线性性，有：

\[\mathbb{E}(T)=\sum_{i=1}^{n-1}\mathbb{E}(X_i) \]

其中 \(\mathbb{E}(X_i)\) 表示从 \(i\) 走到 \(i+1\) 的期望步数。

显然 \(\mathbb E(1)=1\)，考虑递推：

  • 有向左走和向右走两种选择，而向左需要两步才能回到当前点，因此可以得出：

\[\mathbb E(X_i)=\frac{1}{2}\Big(2+\mathbb E(X_{i-1})+\mathbb E(X_i)\Big) \]

解方程可得：

\[\mathbb E(X_i)=2+\mathbb{E}(X_{i-1}) \]

  • 所以最终的答案为：\(\mathbb{E}(T)=\sum_{i=1}^{n-1}2i-1=(n-1)^2\)。

完全图随机游走

  • 在一张 \(n\) 个点的完全图上游走，求从 \(x\) 走到 \(y\) 的期望步数。

如果 \(x=y\) 那么 \(\mathbb{E}(x\rightarrow y)=0\)。

否则每轮都有 \(\frac{1}{n-1}\) 的概率抵达 \(y\)， 所以 \(\mathbb{E}(x\rightarrow y)=n-1\)。

完全二分图随机游走

  • 在一张 \(2n\) 个点的完全二分图上游走，求 \(x\) 走到 \(y\) 的期望步数。

令 \(A\) 为点 \(p\) 到其指定异侧点的期望步数，\(B\) 为点 \(p\) 到其指定同侧点的期望步数。

  • 显然点 \(p\) 到其指定异侧点的步数为 \(1\)，其他异侧点为 \(1+B\)，又有 \(B=1+A\)，可得方程组：

\[\begin{cases}A=\frac{1}{n}\times 1+\frac{n-1}{n}\times(1+B)\\B=1+A\end{cases} \]

解得：

\[\begin{cases}A=2n-1\\B=2n\end{cases} \]

菊花图随机游走

  • 在一张 \(n\) 个点的菊花图上游走，求 \(x\) 走到 \(y\) 的期望步数。

显然有叶子点到中心点的期望为 \(1\)。

令 \(A\) 为中心点到其指定叶子点的期望步数，\(B\) 为叶子点到其指定叶子点的期望步数，可得方程组：

\[\begin{cases}A=\frac{1}{n-1}\times 1+\frac{n-2}{n-1}\times(1+B)\\B=1+A\end{cases} \]

解得：

\[\begin{cases}A=2n-3\\B=2n-2\end{cases} \]

树上随机游走

  • 在一棵 \(n\) 个点的树上游走，求 \(x\) 走到 \(y\) 的期望步数。

以 \(x\) 为根，考虑 \(y\) 走到 \(x\) 的期望步数.

设 \(f_u\) 为 \(u\) 走到 \(u\) 父亲的期望步数，可得：

\[f_u=1+\frac{1}{deg_u}\sum_{v\in u.son} (f_u+f_v) \]

\[\frac{1}{deg_u}f_u=1+\sum_{v\in u.son} f_v \]

\[f_u=deg_u+\sum_{v\in u.son} f_v \]

深搜一遍即可。

高斯约旦消元

传送门

Description

解一个 \(n\) 元线性方程组。

Solution

  1. 选择一个尚未被选过的未知数作为主元，选择一个包含这个主元的方程。

  2. 将这个方程主元的系数化为1。

  3. 通过加减消元，消掉其它方程中的这个未知数。

  4. 重复以上步骤，直到把每一行都变成只有一项有系数。

  • 高斯约旦消元法的实质是将一个 \(n\times(n+1)\) 的矩阵化为对角线形式，即：

\[\begin{Bmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,n}\ |\ a_{1,n+1}\\a_{2,1}&a_{2,2}&\cdots&a_{2,n}\ |\ a_{1,n+1}\\\vdots&\vdots&\ddots\\a_{n,1}&a_{n,2}&&a_{n,n}\ |\ a_{n,n+1}\end{Bmatrix}\Rightarrow\begin{Bmatrix}1&0&\cdots&0\ |\ a'_{1,n+1}\\0&1&\cdots&0\ |\ a'_{1,n+1}\\\vdots&\vdots&\ddots\\0&0&&1\ |\ a'_{n,n+1}\end{Bmatrix} \]

时间复杂度为 \(O(n^3)\)。

Code

const int N=1e2+5;
const double eps=1e-6;
int n;
double a[N][N];
bool p;

inline void Gauss(){
    for(int i=1;i<=n;i++){
        int r=i;
        for(int j=i+1;j<=n;j++)
            if(fabs(a[r][i])<fabs(a[j][i]))
                r=j;
        if(r!=i)
            for(int j=1;j<=n+1;j++)
                swap(a[i][j],a[r][j]);
        if(fabs(a[i][i])<eps){
            p=true;
            return;
        }
        for(int j=1;j<=n;j++)
            if(j!=i){
                double tmp=a[j][i]/a[i][i];
                for(int k=i+1;k<=n+1;k++)
                    a[j][k]-=a[i][k]*tmp;
            }
    }
    for(int i=1;i<=n;i++)
        a[i][n+1]/=a[i][i];
}

signed main(){
    n=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n+1;j++)
            scanf("%lf",&a[i][j]);
    Gauss();
    if(p){
        printf("No Solution\n");
        return 0;
    }
    for(int i=1;i<=n;++i)
        printf("%.2lf\n",a[i][n+1]);
    return 0;
}

例题

P1297 [国家集训队] 单选错位

传送门

Description

每道单选题都选择了正确的答案，但错位填涂，求最终做对题目的期望。

Solution

考虑每个选项对于答案的贡献，已知第 \(i\) 道题目的选项数为 \(a_i\)，那么做对这道题目的概率为 \(\frac{\min(a_i,a_{i-1})}{a_i\times a_{i-1}}=\frac{1}{\max(a_i,a_{i-1})}\)。

答案取和即可。

Code


const int N=1e7+5;
const int mod=1e8+1;
int n,A,B,p,a[N];

double ans;

signed main(){
    n=read();A=read();B=read();p=read();a[1]=read();
    for(int i=2;i<=n;i++)
        a[i]=(a[i-1]*A+B)%mod;
    for(int i=1;i<=n;i++)
        a[i]=a[i]%p+1;
    ans+=1.0/(double)max(a[1],a[n]);
    for(int i=2;i<=n;i++)
        ans+=1.0/(double)max(a[i],a[i-1]);
    printf("%.3lf",ans);
    return 0;
}

P3802 小魔女帕琪

传送门

Description

有 \(7\) 个魔法，给定每个魔法的数量，求将所有魔法放完后连续 \(7\) 个魔法种类不同数量期望。

Solution

考虑对于取的连续 \(7\) 个魔法：

  • 设 \(tot=\sum_{i=1}^7 a_i\)。

那么连续 \(7\) 个魔法互不相同的概率为 \(7!\times\prod_{i=1}^7 \frac{a_i}{tot-i+1}\)。

共有 \((tot-6)\) 个连续段，因此 \(ans=(tot-6)\times 7!\times\prod_{i=1}^7 \frac{a_i}{tot-i+1}\)。

Code

inline void write(int num){
    if(num<0)static_cast<void>(putchar('-')),num=-num;
    if(num>9)write(num/10);
    putchar(num%10+48);
}

const int N=8;
int a[N],tot;
double ans=1;

signed main(){
    for(int i=1;i<=7;i++)
        a[i]=read(),tot+=a[i];
    for(int i=1;i<=6;i++)
        ans=ans*a[i]/(tot+1-i)*double(i);
    ans=ans*a[7]*7.0;
    printf("%.3lf\n",ans);
    return 0;
}

P5081 Tweetuzki 爱取球

传送门

Description

有一个袋子，袋子中有 \(n\) 个无差别的球。每次随机取出一个球后放回。求取遍所有球的期望次数。

Solution

  • 对于一个实验，有 \(p\) 的概率成功 \((0<p\leq1)\)，不成功的概率为 \((1-p)\)。如果一次试验后不成功则重复进行试验，否则停止。那么实验成功的期望次数为 \(\frac{1}{p}\)。

证明：根据期望的线性性，设期望 \(x\) 步后停止试验，可得方程：

\[x=1+p\times 0+(1-p)\times x \]

解得：

\[x=\frac{1}{p} \]

  • 由此考虑每次摸球的概率：

首先有 \(n\) 个球没有被摸到的时候，摸一次摸到新球的概率为 \(\frac{n-0}{n}\)，根据引理，期望摸 \(\frac{n}{n-0}\) 次；

然后有 \(n-1\) 个球没有被摸到的时候，摸一次摸到新球的概率为 \(\frac{n-1}{n}\)，根据引理，期望摸 \(\frac{n}{n-1}\) 次……

归纳可得：\(ans=\sum_{i=1}^n \frac{n}{i}\)。

Code

const int N=1e7+5;
const int p=20040313;
int n,inv[N],sum;

signed main(){
    n=read();
    inv[1]=1;sum+=1;
    for(int i=2;i<=n;i++)
        inv[i]=(1ll*(p-p/i)*inv[p%i])%p,sum=(sum+inv[i])%p;
    write(n*sum%p);
    return 0;
}

P3924 康娜的线段树

传送门

Description

每次在线段树区间加操作做完后，从根节点开始等概率的选择一个子节点进入，直到进入叶子结点为止，将一路经过的节点权值累加，求最后能得到的期望值是多少。

Solution

  • 对于一个线段树上的叶子节点，它对它所有的祖先都有贡献。

假定当前节点的深度为 \(depth\)，那么访问它的概率就是 \(\frac{1}{2^{depth}}\)。

于是考虑深度为 \(depth\) 的叶子结点 \(i\) 对答案的贡献，为 \(a_i\times\sum_{i=0}^{depth}\frac{1}{2^{i}}=a_i\times (2-\frac{1}{2^{depth}})\)。

对于每个结点，它的 \(depth\) 都是确定，所以可以 \(O(n)\) 统计出最初的答案。

  • 考虑每次修改产生的贡献：

设 \(l,r,x\) 为在区间 \([l,r]\) 内的每个元素加上 \(x\) 的操作。

则答案增大了 \(x\sum_{i=l}^{r}(2-\frac{1}{2^{depth_i}})\)。

这是个前缀和的形式，直接维护 \((2-\frac{1}{2^{depth_i}})\)即可。

Code

const int N=1e6+5;
int a[N],depth[N],mxdep=20;
int s[N],ans,bas[N],k,n,m,l,r,x;

inline void build(int p,int l,int r,int d){
    if(l==r){
        depth[l]=d;
        s[l]=2*bas[mxdep]-bas[mxdep]/bas[d];
        ans+=a[l]*s[l];
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid,d+1);
    build(p<<1|1,mid+1,r,d+1);
//    pushup(p);
}

inline int gcd(int a,int b){
    int temp;
    while(b){
        temp=b;
        b=a%b;
        a=temp;
    }
    return a;
}

signed main(){
    n=read();m=read();k=read();bas[0]=1;
    for(int i=1;i<=20;i++)
        bas[i]=2*bas[i-1];
    for(int i=1;i<=n;i++)
        a[i]=read();
    build(1,1,n,0);
    for(int i=1;i<=n;i++)
        s[i]=s[i]+s[i-1];
    int g=gcd(k,bas[mxdep]);k/=g;bas[mxdep]/=g;
    while(m--){
        l=read();r=read();x=read();
        ans+=x*(s[r]-s[l-1]);
        write(ans*k/bas[mxdep]);puts("");
    }
    return 0;
}

P6024 机器人

传送门

Description

每个任务有两种属性：完成需要花的钱 \(w_i\)，成功率 \(p_i\)。
将任务按一定顺序排序后，机器人将按如下方式做任务：

  • 从第一个任务开始做；
  • 花费代价做完第 \(i\) 个任务后，如果成功，则继续做第 \(i+1\) 个任务，否则重新从第一个任务开始做；
  • 成功做完第 \(n\) 个任务后，流程结束。

找到一种排列顺序，使得他的期望花费最小。

Solution

无解的情况肯定是有事件的成功概率为 \(0\)。

  • 考虑计算某种顺序下的期望花费：

\[\begin{aligned}\mathbb E&=(1-p_1)(w_1+\mathbb E)+p_1(1-p_2)(w_1+w_2+\mathbb E)+\cdots+p_1p_2\cdots p_n(w_1+w_2+\cdots+w_n)\\&=(1-p_1p_2\cdots p_n)\mathbb E+(w_1+p_1w_2+p_1p_2w_3+\cdots+p_1p_2\cdots p_{n-1}w_n)\end{aligned} \]

\[\mathbb E=\dfrac{w_1+p_1w_2+p_1p_2w_3+\cdots+p_1p_2\cdots p_{n-1}w_n}{p_1p_2\cdots p_n} \]

我们考虑交换第一件事与第二件事:

\[\mathbb E'=\dfrac{w_2+p_2w_1+p_1p_2w_3+\cdots+p_1p_2\cdots p_{n-1}w_n}{p_1p_2\cdots p_n} \]

若 \(\mathbb E>\mathbb E'\) 则 \(w_1+p_1w_2>w_2+p_2w_1\)。即 \(\dfrac{w_2}{1-p_2}<\dfrac{w_1}{1-p_1}\)。

  • 同理可得相邻两个事件交换后期望花费变小等价于 \(\dfrac{w}{1-p}\) 反序，因此最小值必定在 \(\dfrac{w}{1-p}\) 升序时得到。

Code

const int N=2e5+5;

struct node{
    int id;
    int w,p;
}a[N];

int n;

inline bool cmp(node a,node b){
    return a.w*(10000-b.p)<b.w*(10000-a.p);
}

signed main(){
    n=read();
    for(int i=1;i<=n;i++)
        a[i].id=i;
    for(int i=1;i<=n;i++)
        a[i].w=read();
    for(int i=1;i<=n;i++){
        a[i].p=read();
        if(a[i].p==0){
            printf("Impossible");
            return 0;
        }
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++)
        write(a[i].id),putchar(' ');
    return 0;
}

P1654 OSU!

传送门

Description

一共有 \(n\) 次操作，每次操作只有成功与失败之分，成功对应 \(1\)，失败对应 \(0\)，\(n\) 次操作对应为 \(1\) 个长度为 \(n\) 的 01 串。在这个串中连续的 \(X\) 个 \(1\) 可以贡献 \(X^3\) 的分数，这 \(x\) 个 \(1\) 不能被其他连续的 \(1\) 所包含。

现在给出 \(n\)，以及每个操作的成功率，输出期望分数。

Solution

  • 有 \((x+1)^2=x^2+2x+1\)。
  • 有 \((x+1)^3=x^3+3x^2+3x+1\)。

考虑每个事件对期望的贡献，每个幂单独计算：

\[x1_i=p_i\times(x1_{i-1}+1) \]

\[x2_i=p_i\times(x2_{i-1}^2+2x1_{i-1}+1) \]

\[x3_i=p_i\times(x3_{i-1}^3+3x2_{i-1}^2+3x1_{i-1}+1) \]

答案为 \(x3_n\)。

Code

double a,x,x2,x3;
int n;

signed main(){
    n=read();
    for(int i=1;i<=n;i++){
        scanf("%lf",&a);
        x3=x3+a*(3*x2+3*x+1);
        x2=a*(x2+2*x+1);
        x=a*(x+1);
    }
    printf("%.1lf",x3);
    return 0;
}

CF280C Game on Tree

传送门

Description

给定一棵大小为 \(n\) 的树，每次可以选择一个白点并将其子树染黑，求期望多少次使得所有点都变黑。

Solution

问题等价于求所有点的期望被操作次数和，根据期望的线性性，我们有：

\[\mathbb{E}(T)=\sum\mathbb{E}(X_i) \]

其中 \(\mathbb{E}(X_i)\) 表示点 \(i\) 的操作次数。

  • 考虑随机生成一个 \(1\sim n\) 的排列，根据排列左到右枚举点，如果没有被染黑就把它染黑。一个点被染黑当且仅当它的祖先结点都排在它的后面，因此该点被染黑的概率为 \(\frac{1}{depth_i}\)。

综上答案为 \(\sum \frac{1}{depth_i}\)。

Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

typedef long long LL;

inline int read(){
    int s=0,f=1;char ch=getchar();
    while(ch<'0' or ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' and ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
    return f*s;
}

inline void write(int num){
    if(num<0)static_cast<void>(putchar('-')),num=-num;
    if(num>9)write(num/10);
    putchar(num%10+48);
}

const int N=2e5+5;
int n,m,r,mod,a[N];
int head[N],cnt,depth[N];
double ans;

struct Edge{
    int nxt,to;
}edge[N<<1];

inline void add(int u,int v){
    edge[++cnt]=(Edge){head[u],v};
    head[u]=cnt;
}

inline void dfs(int u,int f){
    depth[u]=depth[f]+1;
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(v==f)
            continue;
        dfs(v,u);
    }
}

signed main(){
    n=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        add(u,v);add(v,u);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
        ans+=1.0/depth[i];
    printf("%lf",ans);
    return 0;
}

P4284 [SHOI2014] 概率充电器

传送门

Description

给定一棵树，大小为 \(n\)，每个点有 \(p_i\) 的概率充电，每条边有 \(q_{i,j}\) 的概率通电，求有多少个点充电。

Solution

先建立一个超级源点 \(S\)，连接 \(i\to S\)，\(val_{i\to s}=p_i\)，问题等价于期望多少个点与 \(S\) 联通。

根据期望的线性性：\(\mathbb{E}(T)=\sum\mathbb{E}(X_i)\)，只需要考虑每个点连接到 \(S\) 的概率和即可。

  • 考虑容斥：

不妨统计 \(f_i\) 表示 \(i\) 没有连接到 \(S\) 的概率，那么问题等价于求保留所有联通块并计算贡献 \(\prod q_{u,v}\cdot\prod(1-p_i)\)。

  • 考虑通过换根 dp 统计：

先设 \(dp_i\) 表示第 \(i\) 个节点在考虑自身及其子树有电的概率。

  • 要让 \(i\) 没电，就要求它自己没电，它的儿子也全部没电，或者有电的孩子和 \(i\) 之间的导线不导电。

本身 \(i\) 没电的概率是 \((1-p_i)\)，孩子 \(v\) 没电的概率是 \(dp_v\)，孩子 \(v\) 有电并且 \((i,v)\) 不导电的概率是 \((1-dp_v)(1-q_{i,v})\)，那么孩子 \(v\) 到 \(i\) 这一段没电的概率就是 \(dp_v+(1-dp_v)(1-q_{i,v})\)。

将每个儿子的贡献相乘，可得出以下式子：

\[dp_i=(1-p_i)\prod_{v\in i.edge}\Big(dp_v+(1-dp_v)\times(1-q_{i,v})\Big) \]

  • 发现每个孩子对于答案的贡献是独立的。

于是点 \(i\) 除去孩子 \(v\) 之后，剩下部分没有通电的概率为 \(\frac{dp_i}{dp_v+(1-dp_v)\times(1-q_{i,v})}\)。

然后考虑换根还原，即 \(fa_i\) 对 \(i\) 的影响：

  • 记 \(DP_i\) 为点 \(fa_i\) 没有电传到 \(i\) 的概率，记：

\[T=DP_{fa_i}+\frac{dp_{fa_i}}{dp_i+(1-dp_i)\times(1-q_{fa_i,i})} \]

也就是 \(fa_i\) 不算 \(i\) 这棵子树，剩下的部分使得 \(fa_i\) 没电的概率。

那么有：

\[DP_i=T+(1-T)\times(1-q_{fa_i,i}) \]

\((1-T)\) 为 \(fa_i\) 不算 \(i\) 这棵子树，剩下的部分使得 \(fa_i\) 有电的概率，\((1-q_{fa_i,i})\) 为 \((fa_i,i)\) 边不导电的概率，那么整个就是 \(fa_i\) 有电并且 \((fa_i,i)\) 没电的概率。

  • 因此，点 \(i\) 没电的总概率为 \(dp_i\times DP_i\)，那么点 \(i\) 有电点概率就是 \(1-dp_i\times DP_i\)。

所以 \(ans=\sum_{i=1}^{n}(1-dp_i\times DP_i)\)。

Code

const int N=5e5+5;

int n;
int head[N],cnt,depth[N];
int vis[N],fa[N];
double p[N],g[N],fv[N],dps[N],dpf[N],ans;

struct Edge{
    int nxt,to;
    double val;
}edge[N<<1];

inline void add(int u,int v,int w){
    edge[++cnt]=(Edge){head[u],v,0.01*w};
    head[u]=cnt;
}

inline void dfs(int u,int f){
    dps[u]=1-p[u];
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(v==f){
            fa[u]=v;fv[u]=edge[i].val;
            continue;
        }
        dfs(v,u);
        Merge(u,v,edge[i].val);
    }
}

inline void dfs2(int u){
    if(fa[u]){
        if(g[u])
            dpf[u]=dpf[fa[u]]*dps[fa[u]]/g[u]+(1-dpf[fa[u]]*dps[fa[u]]/g[u])*(1-fv[u]);
    }else
        dpf[u]=1;
    ans+=1-dps[u]*dpf[u];
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(v==fa[u])
            continue;
        dfs2(v);
    }
}

signed main(){
    n=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        add(u,v,w);add(v,u,w);
    }
    for(int i=1;i<=n;i++)
        p[i]=0.01*read();
    dfs(1,0);dfs2(1);
    printf("%lf",ans);
    return 0;
}

P3232 [HNOI2013] 游走

传送门

Description

给一张图 \(G=(V,E)\)，让你将 \(\{V\}\) 按 \(1\sim m\) 编号，在图上随机游走，求 \(1\rightarrow n\) 的序号和期望的最小值。

Solution

  • 首先贪心地想，一条边的期望经过次数越大，它的编号一定越小。

因此题目转化成了求边的期望经过次数。

发现边的期望不好求，于是可以先求点的期望，再将其转化到边上。

  • 令 \(f_i\) 为 \(i\) 号点期望经过次数，那么有：

\[f_i=\begin{cases}\sum_{(i,j)\in E,j\ne n} \frac{f_j}{deg_j}+1&(i=1)\\\sum_{(i,j)\in E,j\ne n} \frac{f_j}{deg_j}&(1<i<n)\end{cases} \]

由于到点 \(n\) 就停止游走，因此不能考虑点 \(n\) 的贡献。上面这一块是个 \((n-1)\) 元的线性方程组，用高斯消元求出每个 \(f_i\)。

考虑每条边的贡献，相当于其两个端点的贡献与度数的积之和。

  • 令 \(g_i\) 为 \(i\) 号边期望经过次数，那么有：

\[g_i=\frac{f_u}{deg_u}[u\ne n]+\frac{f_v}{deg_v}[v\ne n] \]

将 \(g\) 从大到小排序，期望越大的边标号越小。

Code

const int N=505,M=5e5+5;
const double eps=1e-6;
int n,m,head[N],cnt;
int deg[N],st[M],ed[M];
double f[M];

struct Edge{
    int nxt,to;
}edge[M];

double a[N][N],ans;

inline void Gauss(int lim){
    for(int i=1;i<=lim;i++){
        int r=i;
        for(int j=i+1;j<=lim;j++)
            if(fabs(a[r][i])<fabs(a[j][i]))
                r=j;
        if(r!=i)
            for(int j=1;j<=lim+1;j++)
                swap(a[i][j],a[r][j]);
        for(int j=1;j<=lim;j++)
            if(j!=i){
                double tmp=a[j][i]/a[i][i];
                for(int k=i+1;k<=lim+1;k++)
                    a[j][k]-=a[i][k]*tmp;
            }
    }
    for(int i=1;i<=lim;i++)
        a[i][lim+1]/=a[i][i];
}

inline void add(int u,int v){
    edge[++cnt]=(Edge){head[u],v};
    head[u]=cnt;
}

signed main(){
    n=read();m=read();
    for(int i=1;i<=m;i++){
        st[i]=read();ed[i]=read();
        add(st[i],ed[i]);add(ed[i],st[i]);
        deg[st[i]]++;deg[ed[i]]++;
    }
    for(int u=1;u<n;u++){
        a[u][u]=1.0;
        for(int i=head[u];i;i=edge[i].nxt){
            int v=edge[i].to;
            if(v==n)
                continue;
            a[u][v]=-1.0/deg[v];
        }
    }
    a[1][n]=1;
    Gauss(n-1);
    for(int i=1;i<=m;i++){
        int u=st[i],v=ed[i];
        if(u!=n)
            f[i]+=1.0*a[u][n]/deg[u];
        if(v!=n)
            f[i]+=1.0*a[v][n]/deg[v];
    }
    sort(f+1,f+m+1);
    for(int i=1;i<=m;i++)
        ans+=1.0*(m-i+1)*f[i];
    printf("%.3lf",ans);
    return 0;
}

P3412 仓鼠找sugar II

传送门

Description

给定一棵树，求在树上一任意点到另一任意点随机游走的步数期望。

Solution

深搜一遍可得到：

\[f_u=deg_u+\sum_{v\in u.son} f_v \]

对于每一个结点 \(u\)，有 \(size_u\) 个点必须经过它才能到根节点。

  • 枚举每个节点作为根节点，树形 dp \(n\) 次。

那么 \(ans=\sum_{root}\sum_{i=1}^n f_i\times size_{i}\)

这个东西是 \(O(n^2)\) 的。考虑优化为 \(O(n)\)。

  • 考虑所有情况下的 \(\{f\}\) 和 \(\{size\}\) 对答案的贡献。

先以 \(1\) 号节点为根建立一棵有根树，对于每个节点维护其子树大小（\(\{s\}\)）和子树内度数和（\(\{sumd\}\)）。

令 \(totd=\sum d\)。

对于每一个节点 \(u\)，分三类情况讨论：

  1. 若该节点就是终点，则 \(f_u=0,size_u=n\)，它会对答案贡献 \(1\) 次。

  2. 若终点在该节点的某一个儿子的子树 \(v\) 中，则 \(f_u=totd-sumd_v,size_u=n-s_v\)，它会对答案贡献 \(s_v\) 次。

  3. 若终点不在该节点的任何一个儿子的子树中，则 \(f_u=sumd_v,size_u=s_v\)，它会对答案贡献 \(n-s_v\) 次。

  • 最后对于每一个节点直接统计即可。

Code

const int N=1e5+5;
const int mod=998244353;
int n,head[N],siz[N],fa[N],cnt,d[N],totd,ans,inv;

struct Edge{
    int nxt,to;
}edge[N<<1];

inline void add(int u,int v){
    edge[++cnt]=(Edge){head[u],v};
    head[u]=cnt;
}

inline void dfs(int u,int f){
    fa[u]=f;siz[u]=1;
    for(int i=head[u];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(v==f)
            continue;
        dfs(v,u);
        siz[u]+=siz[v];
        d[u]+=d[v];
    }
}

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

signed main(){
    n=read();inv=qpow(1ll*n*n%mod,mod-2);
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        add(u,v);add(v,u);
        d[u]++;d[v]++;
    }
    for(int i=1;i<=n;i++)
        totd+=d[i];
    dfs(1,0);
    for(int u=1;u<=n;u++)
        for(int i=head[u];i;i=edge[i].nxt){
            int v=edge[i].to;
            if(v==fa[u])
                ans=(ans+1ll*d[u]*siz[u]%mod*(n-siz[u])%mod)%mod;
            else
                ans=(ans+1ll*(totd-d[v])*(n-siz[v])%mod*siz[v]%mod)%mod;
        }
    write(1ll*ans*inv%mod);
    return 0;
}

标签：mathbb,frac,入门,int,sum,times,期望,进门
From： https://www.cnblogs.com/QcpyWcpyQ/p/18017003

相关文章

  • HydroOJ 从入门到入土（13）批量修改题号前缀
    题库的管理，无论是用前缀来分组，还是用域来分组，都有不好管理的地方，尤其是题号。有的时候导入了一堆题，导入完发现题号不是自己想要的，但删起来很麻烦，一个一个改更不现实，真是欲哭无泪。本文主要记录了一次批量修改题号前缀的过程，仅供参考。修改中涉及数据库操作，修改前一定要现在虚......
  • 拓扑排序入门
    目录写在前面一些概念算法步骤字典序最大/最小的拓扑序列？模板例题3704.排队家谱树奖金P1983[NOIP2013普及组]车站分级1639.拓扑顺序写在前面昨晚cfdiv3的F就是一道基本上可以说板子的拓扑排序的题目，没有做出来感觉图论很早之前就看了，但是基本没有刷过什么题，开始补一下图论......
  • 掌握C语言文件操作：从入门到精通的完整指南！
    ✨✨欢迎大家来到贝蒂大讲堂✨✨......
  • pytorch深度学习入门（8）之-Torchaudio使用Tacotron2 文本转语音
    https://blog.csdn.net/ajunbin859/article/details/134380417?ops_request_misc=&request_id=&biz_id=102&utm_term=pytorch%E7%89%88%E6%9C%AC%E7%9A%84tacotron%E8%AF%A6%E7%BB%86%E5%AE%89%E8%A3%85%E6%95%99%E7%A8%8B&utm_medium=distribute.pc_search_r......
  • day04_操作系统入门
    今日笔记学操作系统基础概念linux系统linux系统(centos)+vmware安装起来（网络配置，磁盘分区）ubuntu安装xshell服务器的远程连接服务器网站的前后端，数据库app的前后端，数据库微信、腾讯微信的服务器移动端设备上，安装的微信客户端在线笔记笔记对运维来说，就是一个宝藏，mar......
  • day21_乌班图入门
    .请解释yum缓存，如何理解、如何管理去网络源下载软件rpm包，会涉及网络延时，网络资源消耗1.解决，关于yum缓存包的理解（自己搭建yum仓库）11.当你拿到一个初始化的机器，默认安装的软件（centos上的rpm格式的软件）数量可能很少导致你后期使用各种工具，会报错，比如python调用gzip解压缩功能s......
  • Python语言程序设计入门教程
      目  录第一章、概述    1.Python是什么    2.Python语言的特点    3.Python语言的缺点    4.Python程序的执行过程10   5.安装Python11  6.运行Python程序17        7.Python集成开发环境21  第二章、......
  • 第十九天：Mysql基础入门
    一、关系型数据库基础1、数据的分类结构化的数据   非结构化的数据  半结构化数据2、关系型数据库RDBMS （1）常用关系数据库 MySQL:MySQL,MariaDB,PerconaServerPostgreSQL:简称为pgsql，EnterpriseDBOracleMSSQLServerDB23、数......
  • Linux Bash Shell 脚本入门（2）——GNU
    ​LinuxBashShell脚本入门（2）——GNU目录LinuxBashShell脚本入门（2）——GNUGNU与LinuxGNUGNU的组成ShellGNOME桌面环境XWindow软件GNOME可点击内容，大部分来自维基百科，可以点击了解详情。GNU与LinuxGNUGNU操作系统起源于GNU计划，由理查德·斯托曼在麻省理工学院人工智能......
  • 小白入门clang_format
    如果没时间研究折腾，可以接受这样↓的风格 那么安装这个↓，默认在代码界面按alt+shift+f即可 ========================================================== 如果你想稍微个性化一点在上面的基础上，做以下配置 什么意思自己看上面↑截图的文字介绍 如何回到代码界面按a......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99