《期望與機率練習》

寫着寫着拿出了我的機率論書（哭

連續性随機變量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的使用,含測試工程