《期望与概率练习》

写着写着拿出了我的概率论书（哭

连续性随机变量X的期望：$E[X] = \sum_{x = -INF}^{INF} x * f(x) dx $ - f(x)为概率密度.

https://www.luogu.com.cn/problem/P4316:

一开始写了个暴力，结果过了？可能DAG不太好卡暴力吧。

《期望与概率练习》

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,double> pii2;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const LL Mod = 1e9 + 7;
#define dbg(ax) cout << "now this num is " << ax << endl;
inline long long ADD(long long x,long long y) {
    if(x + y < 0) return ((x + y) % Mod + Mod) % Mod;
    return (x + y) % Mod;
}
inline long long MUL(long long x,long long y) {
    if(x * y < 0) return ((x * y) % Mod + Mod) % Mod;
    return x * y % Mod;
}
inline long long DEC(long long x,long long y) {
    if(x - y < 0) return (x - y + Mod) % Mod;
    return (x - y) % Mod;
}

vector<pii> G[N];
vector<pii2> vec[N];
int in[N];
void solve() { 
    int n,m;scanf("%d %d",&n,&m);
    while(m--) {
        int u,v,w;scanf("%d %d %d",&u,&v,&w);
        G[u].push_back(pii{v,w});
        in[v]++;
    }
    queue<int> Q;
    Q.push(1);
    vec[1].push_back(pii2{0,1});
    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();
        double p = 1.0 / G[u].size();
        for(auto v : G[u]) {
            in[v.first]--;
            for(auto tt : vec[u]) {
                vec[v.first].push_back(pii2{tt.first + v.second,tt.second * p});
            }
            if(in[v.first] == 0) Q.push(v.first);
        }
    }
    double ans = 0;
    for(auto v : vec[n]) ans += v.first * v.second;
    printf("%.2f\n",ans);
}   
int main() {
    solve();
    //system("pause");
    return 0;
}

View Code

正解：考虑期望dp。

因为是从1 -> n，所以可以定义dp[i] = i走到n的期望路径长度。

那么显然可以有dp[n] = 0，所以很显然我们要逆推，所以要建反图。

$dp[u] = \sum (dp[v] + w[u -> v]) * p$需要注意的是这里的p应该是v到u的概率，因为虽然我们是逆推的，但是实际上我们是正着走的。

然后也不难理解，如果转移成功能获得的贡献是$dp[v] + w[u -> v]$

《期望与概率练习》

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,double> pii2;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const LL Mod = 1e9 + 7;
#define dbg(ax) cout << "now this num is " << ax << endl;
inline long long ADD(long long x,long long y) {
    if(x + y < 0) return ((x + y) % Mod + Mod) % Mod;
    return (x + y) % Mod;
}
inline long long MUL(long long x,long long y) {
    if(x * y < 0) return ((x * y) % Mod + Mod) % Mod;
    return x * y % Mod;
}
inline long long DEC(long long x,long long y) {
    if(x - y < 0) return (x - y + Mod) % Mod;
    return (x - y) % Mod;
}

vector<pii> G[N];
int in[N],sz[N];
double dp[N];
void solve() { 
    int n,m;scanf("%d %d",&n,&m);
    while(m--) {
        int u,v,w;scanf("%d %d %d",&u,&v,&w);
        G[v].push_back(pii{u,w});
        in[u]++,sz[u]++;
    }
    queue<int> Q;
    Q.push(n);
    dp[n] = 0;
    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for(auto v : G[u]) {
            in[v.first]--;
            dp[v.first] +=  (dp[u] + v.second) * (1.0 / sz[v.first]);
            if(in[v.first] == 0) Q.push(v.first);
        }
    }
    printf("%.2f\n",dp[1]);
}   
int main() {
    solve();
    //system("pause");
    return 0;
}

https://www.luogu.com.cn/problem/P5104:

这么大的数据只能基于矩阵快速幂去考虑，但是由于这里是对于连续形状随机变量而言，也不好dp。

我们首先可以计算第一个取的人的期望钱数.$E1 = \sum_{x = 0}^{w} x \frac{1}{w} dx = \frac{1}{2} w$

因为E1 = w / 2，所以w - E1 = E1

我们继续第二个人的期望钱数$E2 = \sum_{x = 0}^{E1} x \frac{1}{E1} dx = \frac{1}{2} E1$

由此可见后面的递推都是1 / 2，那么可得第k个人的期望钱数 = w / 2 ^ k

《期望与概率练习》

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,double> pii2;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const LL Mod = 1e9 + 7;
#define dbg(ax) cout << "now this num is " << ax << endl;
inline long long ADD(long long x,long long y) {
    if(x + y < 0) return ((x + y) % Mod + Mod) % Mod;
    return (x + y) % Mod;
}
inline long long MUL(long long x,long long y) {
    if(x * y < 0) return ((x * y) % Mod + Mod) % Mod;
    return x * y % Mod;
}
inline long long DEC(long long x,long long y) {
    if(x - y < 0) return (x - y + Mod) % Mod;
    return (x - y) % Mod;
}

LL quick_mi(LL a,LL b) {
    LL re = 1;
    while(b) {
        if(b & 1) re = re * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return re;
}
void solve() { 
    LL w,n,k;scanf("%lld %lld %lld",&w,&n,&k);
    LL ma = quick_mi(2,k);
    LL ans = MUL(w,quick_mi(ma,Mod - 2));
    printf("%lld\n",ans);

}   
int main() {
    solve();
    system("pause");
    return 0;
}

https://www.luogu.com.cn/problem/P6154:

$DAG上的随机游走：考虑每条边的贡献即可。$

$对于一条边u -> v，经过这条边的路径数cnt = 原图拓扑到u的次数 * 反图拓扑到v的次数$

$然后每条路径的期望就是 1 * (cnt / sum)$

$这个sum我们只需要第一遍拓扑的时候处理出来即可$

《期望与概率练习》

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,double> pii2;
const int N = 1e5 + 5;
const int M = 1e6 + 5;
const LL Mod = 998244353;
#define dbg(ax) cout << "now this num is " << ax << endl;
inline long long ADD(long long x,long long y) {
    if(x + y < 0) return ((x + y) % Mod + Mod) % Mod;
    return (x + y) % Mod;
}
inline long long MUL(long long x,long long y) {
    if(x * y < 0) return ((x * y) % Mod + Mod) % Mod;
    return x * y % Mod;
}
inline long long DEC(long long x,long long y) {
    if(x - y < 0) return (x - y + Mod) % Mod;
    return (x - y) % Mod;
}

LL quick_mi(LL a,LL b) {
    LL re = 1;
    while(b) {
        if(b & 1) re = re * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return re;
}
LL dp[N],dp2[N],sum = 0;
int in[N],de[N];
vector<int> G[N],RG[N];
void solve() { 
    int n,m;scanf("%d %d",&n,&m);
    while(m--) {
        int x,y;scanf("%d %d",&x,&y);
        G[x].push_back(y);
        RG[y].push_back(x);
        in[y]++,de[x]++;
    }
    queue<int> Q;
    for(int i = 1;i <= n;++i) {
        dp2[i] = 1;
        if(de[i] == 0) Q.push(i);
    }
    while(!Q.empty()) {
        int u = Q.front();
        sum = ADD(sum,dp2[u]);
        Q.pop();
        for(auto v : RG[u]) {
            dp2[v] = ADD(dp2[v],dp2[u]);
            de[v]--;
            if(de[v] == 0) Q.push(v);
        }
    }
    for(int i = 1;i <= n;++i) {
        dp[i] = 1;
        if(in[i] == 0) Q.push(i);
    }
    LL ans = 0;
    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for(auto v : G[u]) {
            ans = ADD(ans,MUL(MUL(dp[u],dp2[v]),quick_mi(sum,Mod - 2)));
            dp[v] = ADD(dp[v],dp[u]);
            in[v]--;
            if(in[v] == 0) Q.push(v);
        }
    }
    printf("%lld\n",ans);
}   
int main() {
    solve();
    system("pause");
    return 0;
}

https://www.luogu.com.cn/problem/P1297:

$不知道为什么这题感觉还是有些难度的，但是我一看到就想到了做法$

$dp[i]表示做了i道题的期望做对题数，递推式：dp[i] = dp[i - 1] + min(a[i],a[i + 1]) / (a[i] * a[i + 1])$

$并不是很难想，相邻的一共答案对应情况有a[i] * a[i + 1]种，并且其中正确的只有min(a[i],a[i + 1])种$

《期望与概率练习》

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,double> pii2;
const int N = 1e7 + 5;
const int M = 1e6 + 5;
const LL Mod = 998244353;
#define dbg(ax) cout << "now this num is " << ax << endl;
inline long long ADD(long long x,long long y) {
    if(x + y < 0) return ((x + y) % Mod + Mod) % Mod;
    return (x + y) % Mod;
}
inline long long MUL(long long x,long long y) {
    if(x * y < 0) return ((x * y) % Mod + Mod) % Mod;
    return x * y % Mod;
}
inline long long DEC(long long x,long long y) {
    if(x - y < 0) return (x - y + Mod) % Mod;
    return (x - y) % Mod;
}

int n,A,B,C,a[N];
void Input() {
    scanf("%d%d%d%d%d", &n, &A, &B, &C, a + 1);
    for (int i = 2; i <= n; i++)
        a[i] = ((long long) a[i - 1] * A + B) % 100000001;
    for (int i = 1; i <= n; i++)
        a[i] = a[i] % C + 1;
}
double dp[N];//做了i道题的期望做对题数
void solve() { 
    Input();
    for(int i = 1;i <= n;++i) {
        if(i == n) {
            dp[i] = dp[i - 1] + 1.0 * min(a[i],a[1]) / (1LL * a[i] * a[1]);
        }   
        else {
            dp[i] = dp[i - 1] + 1.0 * min(a[i],a[i + 1]) / (1LL * a[i] * a[i + 1]);
        }
    }
    printf("%.3f\n",dp[n]);

}   
int main() {
    solve();
    system("pause");
    return 0;
}

https://www.luogu.com.cn/problem/P1291：

$这里就写一下思路了，因为输出太毒瘤了就不写了$

$很显然有一个dp[i] - 抽到i个不同球星的期望次数$

$定义dp[i + 1] = dp[i] + x$

《期望与概率练习》

继续阅读

C++ 多线程用条件变量确定线程的执行顺序而不是使用 sleep(1)

POJ 1284 Primitive Roots (欧拉函数&原根定理)

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

成员函数初始化列表

2021-08-13c++——类之操作符重载

HDOJ 题目3485 Count 101（递推） Count 101

swmm与lisflood-fp源码如何一起编译 CMake命令

Windows下VS开发环境环境安装工程项目设置关于Debug和Release的提示

一文看懂字符串的加减乘除

C++ 第十五周报告1--《冒泡法排序》

C++实现简单顺序表

C经典书籍笔记——C陷阱与缺陷②(语法陷阱之优先级)一、错误案列二、优先级规律

线性表之顺序表的实现

C++判断素数、求最大公约数代码判断一个数是否为素数求两个数的最大公约数

SequoiaDB巨杉数据库C++驱动概述

开源按键组件Multi_Button的使用,含测试工程