概率与期望
本文最后更新于：2017年10月20日 晚上
公式
概率
$P(A)$代表A事件发生的概率，$Ω$为全集。
一、
$1-P(A) = P(Ω-A)$
二、
$2. P(A_1∪A_2)=P(A_1)+P(A_2)-P(A_1∩A_2)$
推论：若$A_1∩A_2 = ∅$，则$P(A_1∪A_2)=P(A_1)+P(A_2)$
三、AB同时发生的概率 = B发生的概率*在B发生下A发生的概率
$P(AB) = P(B)\times P(A|B) = P(A)\times P(B|A)$
期望
随机变量X：是定义在概率空间上的一个函数 $X(w_i) -> k$
期望：定义在一个随机变量X上，写作：$E[X] = \sum P(w_i)\times X(w_i) $
期望是一种加权平均数。
一、期望的可加性
$E[X+Y] = E[X] + E[Y]$
Problems
1.[bzoj 2134] 单选错位
Description
gx和lc去参加noip初赛，其中有一种题型叫单项选择题，顾名思义，只有一个选项是正确答案。
试卷上共有n道单选题，第i道单选题有$a_i$个选项，这$a_i$个选项编号是$1,2……,a_i$，每个选项成为正确答案的概率都是相等的。lc采取的策略是每道题目随机写上$1-a_i$的某个数作为答案选项，他用不了多少时间就能期望做对$\sum_{i=1}^n \frac{1}{a_i}$道题目。gx则是认认真真地做完了这n道题目，可是等他做完的时候时间也所剩无几了，于是他匆忙地把答案抄到答题纸上，没想到抄错位了:
第i道题目的答案抄到了答题纸上的第i+1道题目的位置上，特别地，第n道题目的答案抄到了第1道题目的位置上。现在gx己经走出考场没法改了，不过他还是想知道自己期望能做对几道题目，这样他就知道会不会被lc鄙视了。
我们假设gx没有做错任何题目，只是答案抄错位置了。
Input
n很大，为了避免读入耗时太多，输入文件只有5个整数参数$n, A, B, C, a_1$，由上交的程序产生数列a。
下面给出pascal/C/C++的读入语句和产生序列的语句（默认从标准输入读入）：// for pascal
readln(n,A,B,C,q[1]);
for i:=2 to n do q[i] := (int64(q[i-1]) * A + B) mod 100000001;
for i:=1 to n do q[i] := q[i] mod C + 1;// for C/C++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;选手可以通过以上的程序语句得到n和数列a（a的元素类型是32位整数），n和a的含义见题目描述。
Output
输出一个实数，表示gx期望做对的题目个数，保留三位小数。
Sample Input
3 2 0 4 1Sample Output
1.167Explanation
a[] = {2,3,1}
| 正确答案 | gx的答案 | 做对题目 | 出现概率 |
|---|---|---|---|
| {1,1,1} | {1,1,1} | 3 | 1/6 |
| {1,2,1} | {1,1,2} | 1 | 1/6 |
| {1,3,1} | {1,1,3} | 1 | 1/6 |
| {2,1,1} | {1,2,1} | 1 | 1/6 |
| {2,2,1} | {1,2,2} | 1 | 1/6 |
| {2,3,1} | {1,2,3} | 0 | 1/6 |
共有6种情况，每种情况出现的概率是1/6，gx期望做对(3+1+1+1+1+0)/6 = 7/6题。（相比之下，lc随机就能期望做对11/6题）
Hint
对于100%的数据 $2≤n≤10^7, 0≤A,B,C,a_1≤10^8$
思路
每道题的期望是独立的，当$a_i > a_{i+1}$时，有 $\frac{a_{i+1}}{a_i}$ 的概率选中$1,2……,a_{i+1}$中的一个，这一个正确的概率为$\frac{1}{a_{i+1}}$，选对的概率为$\frac{1}{a_i}$，每道题贡献为1， 每道题期望做对的题目个数为$\frac{1}{a_i}$，当$a_i < a_{i+1}$时同理可得为$\frac{1}{a_{i+1}}$，所以每道题期望做对的题目个数为$\frac{1}{max(a_i,a_{i+1})}$。
Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#define mem(a,b) memset(a,b,sizeof(a))
#define fr(x) freopen(#x ".in","r",stdin);freopen(#x ".out","w",stdout)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef double db;
const int maxn=1e7+10,mod=100000001;
int a[maxn]={0},n,A,B,C;
int read();
int main()
{
// fr();
scanf("%d%d%d%d%d",&n,&A,&B,&C,&a[1]);
for(int i=2;i<=n;i++) a[i]=(1ll*a[i-1]*A+B)%mod;
for(int i=1;i<=n;i++) a[i]=a[i]%C+1;
a[0]=a[n];
db ans=0.0;
for(int i=1;i<=n;i++) ans+=1.0/max(a[i],a[i-1]);
printf("%.3f\n",ans);
// fprintf(stderr,"%.3f s\n",clock()*1.0/CLOCKS_PER_SEC);
return 0;
}
int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*f;
}2.[bzoj 1419] Red is good
题目描述
桌面上有$R$张红牌和$B$张黑牌，随机打乱顺序后放在桌面上，开始一张一张地翻牌，翻到红牌得到$1$美元，黑牌则付出$1$美元。可以随时停止翻牌，在最优策略下平均能得到多少钱。
输入格式
一行输入两个数$R$,$B$,其值在$0$到$5000$之间
输出格式
在最优策略下平均能得到多少钱。
样例输入
5 1样例输出
4.166666提示
输出答案时,小数点后第六位后的全部去掉,不要四舍五入.
思路
考虑dp，$f[i][j]$表示有i张红牌和j张黑牌，在最优策略下平均能得到多少钱，则$f[i][j]=max(0,\frac{i}{i+j}\times (f[i-1][j]+1)+\frac{j}{i+j}\times (f[i][j-1]-1))$，如期望小于0，不取它一定更优，由于每层状态只与上一层有关，用滚动数组优化。
Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#define mem(a,b) memset(a,b,sizeof(a))
#define fr(x) freopen(#x ".in","r",stdin);freopen(#x ".out","w",stdout)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef double db;
const int maxn=5e3+10;
db f[2][maxn];
int R,B;
int read();
int main()
{
// fr();
R=read(),B=read();
bool d=0;
for(int i=1;i<=R;i++)
{
f[d][0]=i;
for(int j=1;j<=B;j++)
{
f[d][j]=max(0.0,i*1.0/(i+j)*(f[d^1][j]+1)+j*1.0/(i+j)*((f[d][j-1])-1));
}
d^=1;
}
printf("%.6f\n",f[d^1][B]-5e-7);
// fprintf(stderr,"%.3f s\n",clock()*1.0/CLOCKS_PER_SEC);
return 0;
}
int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*f;
}3. [bzoj 2438] [中山市选2011]杀人游戏
Description
一位冷血的杀手潜入 Na-wiat，并假装成平民。警察希望能在 N 个人里面，查出谁是杀手。
警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人， 谁是杀手， 谁是平民。 假如查证的对象是杀手， 杀手将会把警察干掉。
现在警察掌握了每一个人认识谁。
每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。
问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？
Input
第一行有两个整数 N,M。
接下来有 M 行，每行两个整数 x,y，表示 x 认识 y（y 不一定认识 x,例如胡锦涛同志） 。
Output
仅包含一行一个实数，保留小数点后面 6 位，表示最大概率。
Sample Input
5 4
1 2
1 3
1 4
1 5Sample Output
0.800000HINT
警察只需要查证 1。假如1是杀手，警察就会被杀。假如 1不是杀手，他会告诉警察 2,3,4,5 谁是杀手。而 1 是杀手的概率是 0.2,所以能知道谁是杀手但没被杀的概率是0.8。
对于100%的数据有 $1≤N ≤ 10 0000,0≤M ≤ 30 0000$。
思路
要使知道谁是杀手的概率最大，需要少问，对于环上的点，只需问一次，所以先Tarjan缩点，入度为0的scc是一定会问的，但有一种特殊情况，如存在一个scc的size为1，入度为0且出度为0或指向的点有其它入边，则知道x-1个就行啦，问的次数需减一。
Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#define mem(a,b) memset(a,b,sizeof(a))
#define fr(x) freopen(#x ".in","r",stdin);freopen(#x ".out","w",stdout)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef double db;
const int maxn=1e5+10;
typedef int INT[maxn];
struct edge
{
int to,next,from;
edge(){}
edge(int to,int next,int from):to(to),next(next),from(from){}
}e[(maxn<<1)+maxn];
INT pre,low,dfn,stack,sccno,in,sz;
bool ins[maxn];
int tot=0,top=0,n,m,sccCnt=0,dfsClock=0;
int read();
void findScc();
void makeScc();
void add(int,int);
void dfs(int);
int main()
{
// fr();
mem(pre,-1);
n=read(),m=read();
for(int i=1,f,t;i<=m;i++)
{
f=read(),t=read();
add(f,t);
}
findScc();
makeScc();
// fprintf(stderr,"%.3f s\n",clock()*1.0/CLOCKS_PER_SEC);
return 0;
}
void add(int from,int to)
{
e[++tot]=edge(to,pre[from],from);pre[from]=tot;
}
void makeScc()
{
int ans=0;
for(int i=1;i<=tot;i++)
{
int ito=e[i].to,ifr=e[i].from;
if(sccno[ifr]^sccno[ito]) in[sccno[ito]]++;
}
for(int i=1;i<=sccCnt;i++) if(!in[i]) ans++;
for(int i=1;i<=n;i++)
{
if(sz[sccno[i]]==1&&!in[sccno[i]])
{
bool flag=true;
for(int j=pre[i];~j;j=e[j].next)
{
int jto=e[j].to;
if(in[sccno[jto]]<=1){flag=false;break;}
}
if(flag){ans--;break;}
}
}
db Ans=1.0*(n-ans)/n;
printf("%.6f\n",Ans);
}
void findScc()
{
dfsClock=sccCnt=0;
mem(low,0),mem(sccno,0),mem(dfn,0),mem(ins,0),mem(stack,0),mem(sz,0),top=0;
for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i);
}
void dfs(int s)
{
dfn[s]=low[s]=++dfsClock;
ins[stack[++top]=s]=true;
for(int i=pre[s];~i;i=e[i].next)
{
int ito=e[i].to;
if(!dfn[ito]) dfs(ito),low[s]=min(low[s],low[ito]);
else if(ins[ito]) low[s]=min(dfn[ito],low[s]);
}
if(low[s]^dfn[s]) return;
sccCnt++;
while(true)
{
int x=stack[top--];
ins[x]=false;
sccno[x]=sccCnt;
sz[sccCnt]++;
if(x==s) break;
}
}
int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*f;
}4. [tyvj 1952] Easy
描述
某一天WJMZBMR在打osu~~~但是他太弱逼了，有些地方完全靠运气:(
我们来简化一下这个游戏的规则
有n次点击要做，成功了就是o，失败了就是x，分数是按comb计算的，连续a个comb就有aa分，comb就是极大的连续o。
比如ooxxxxooooxxx，分数就是22+4*4=4+16=20。
Sevenkplus闲的慌就看他打了一盘，有些地方跟运气无关要么是o要么是x，有些地方o或者x各有50%的可能性，用?号来表示。
比如oo?xx就是一个可能的输入。
那么WJMZBMR这场osu的期望得分是多少呢？
比如oo?xx的话，?是o的话就是oooxx => 9，是x的话就是ooxxx => 4
期望自然就是(4+9)/2 =6.5了
输入格式
第一行一个整数n，表示点击的个数
接下来一个字符串，每个字符都是ox？中的一个
输出格式
一行一个浮点数表示答案
四舍五入到小数点后4位
如果害怕精度跪建议用long double或者extended
测试样例1
输入
4
????输出
4.1250备注
osu很好玩的哦
WJMZBMR技术还行(雾),x基本上很少呢
思路
$f[i]$表示前i个的期望，$g[i]$表示最后comb的期望长度。
Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#define mem(a,b) memset(a,b,sizeof(a))
#define fr(x) freopen(#x ".in","r",stdin);freopen(#x ".out","w",stdout)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef double db;
const int maxn=5e5+10;
int n;
char s[maxn];
db f[maxn],g[maxn];
int read();
int main()
{
// fr();
n=read();
scanf("%s",s+1);
for(int i=1;i<=n;i++)
{
if(s[i]=='x') f[i]=f[i-1],g[i]=0;
else if(s[i]=='o') f[i]=f[i-1]+g[i-1]*2+1,g[i]=g[i-1]+1;
else f[i]=f[i-1]+g[i-1]+0.5,g[i]=(g[i-1]+1)/2;
}
printf("%.4f\n",f[n]);
// fprintf(stderr,"%.3f s\n",clock()*1.0/CLOCKS_PER_SEC);
return 0;
}
int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*f;
}
