首页 > 代码库 > ACM 中的期望，概率 问题
ACM 中的期望，概率 问题
一个简易的入门：点击打开链接
大神的总结：点击打开链接 zerolock
我搞的题目：点击打开链接
前段时间一直在做概率的题目。
一、期望
其中求解期望问题刚开始一直不理解。后来做得多了有感觉。
例：（有放回）
在5件产品有4件正品，1件次品，从中任取2件，记其中含正品的个数个数为随机变量ξ，则ξ的数学期望Eξ是 1.6
在5件产品有4件正品，1件次品，从中任取2件，记其中含正品的个数个数为随机变量ξ，则ξ=2时所取次数的数学期望是1.16
第一个例子是平常学的期望，做一件事情各个结果的可能情况期望。第二个例子是题目出的，做一件事情需要次数的期望。
解决这类问题，对随机变量A、B,有 数学期望E(aA+bB)=aE(A)+bE(b);
有了这个公式你就可以进行将连续的期望问题，转化为独立的状态了，概率就相当于a，b；A，B为变量。变为线性问题。
E1=（1/3）*E1+（1/3）*E2+（1/3）*E3+1 ①
表示 下一次可以走到2或者3或在原地1，每个可能概率是1/3 ,注意是下一次，故要加上1.
对于这类问题有三种，
1 无环直接递推解决，概率DP求期望入门，HDU 4405，POj 2096,HDU 3853
zoj 3640 当终结点不容易确定的时候用记忆化搜索。
2 只是个别点会构成回路 hdu4035 zoj3329
既DP[i]可能由DP[i+k]和DP[i+j]需要求的比如DP[0]决定
相当于概率一直递推下去会回到原点
比如
(1):DP[i]=a*DP[i+k]+b*DP[0]+d*DP[i+j]+c;
但是DP[i+k]和DP[0]都是未知
这时候根据DP[i]的方程式假设一个方程式：
比如:
(2):DP[i]=A[i]*DP[i+k]+B[i]*DP[0]+C[i];
因为要求DP[0],所以当i=0的时候但是A[0],B[0],C[0]未知
对比(1)和(2)的差别
这时候对比(1)和(2)发现两者之间的差别在于DP[i+j]
所以根据(2)求DP[i+j]然后代入(1)消除然后对比(2)就可以得到A[i],B[i],C[i]
然后视具体情况根据A[i],B[i],C[i]求得A[0],B[0],C[0]继而求DP[0]
3 高斯消元解决.......HDU2262 HDU4418
这个没什么说的
4 状态压缩 HDU4336 这个和无环递推一样，不过也可以用容斥的方法。
首先容斥定理相当于是求多个集合的并集，但是因为两两之间有交集所以需要剪掉重复剪掉的部分。当集合个数多于三个的时候又会出现三个集合之间的交集被误剪掉了，或者四个之间的交集部分又重复计算了等等。于是容斥定理就有用了，当集合个数为n时，我们要算总并集，我们就要算所有的一个集合的大小，所有的两个集合的交集的大小，所有的三个的集合交集的大小，直到n个集合的交集的大小，中间偶数个减掉，奇数个加起来就可以了。楼主容斥定理的那个程序用i的二进制表示一个大集合，i中的每个1表示一个小集合。当i++从0到(1<<n-1)就是00...000到11...111变化的过程可以穷举所有的可能交集情况，然后算出它的大小。“cnt&1”就是在判断奇偶，通过加或者减算出并集。
“1.0/sum”是在算包数，就是期望=np，所以n=期望除以概率，这里期望只要是1就可以了。然后就是每种情况求概率的问题了，比如说某种情况是1101，那么就是算1000,0100,0001三种事件同时发生的概率，因为各个事件是独立的，所以直接可以把概率相加得到总的概率。
独立事件概率相加理解：一次取到这几个东西都行的概率。而之前单个概率值是取单个的概率
其中 f[i]+=in[j]*f[i|(1<<j)];可以保证无后向性。
二、概率
poj3744 一条路上有地雷，一个人要通过那必然是都得通过（没有踩到），递推就能解决。使用要矩阵快速幂。注意移位使用本来的数字否则会溢出。
poj3071 足球概率模拟题，注意二进制倍增的过程中三层循环。
CodeForces 148D dp意思是龙在X X情况下胜利的概率，依据题意可以很容易写出。
poj2151 每队均至少做一题的概率P1 减去 每队做题数均在1到N-1之间的概率P2
SGU 495
题意：n个盒子里装有礼物，m个人随机选择礼物，选完之后空盒子放回
问选中的礼物数的期望。
m个人是独立的。
对于每个礼物不被人选中的概率为((n-1)/n)^m
那么不被选中的礼物数的期望就是 n*((n-1)/n)^m
所以答案就是 n-n*((n-1)/n)^m;HDU 4089 dp[i][j]表示队列中有i个人，Tomato排在第j个，能发生所求事件的概率。
转移的时候，考虑的是队头的那个人而不是当前在J这个位置。
j == 1 : dp[i][1] = p1*dp[i][1] + p2*dp[i][i] + p4;
2<=j<=k: dp[i][j] = p1*dp[i][j] + p2*dp[i][j-1] + p3*dp[i-1][j-1] + p4;
j > k : dp[i][j] = p1*dp[i][j] + p2*dp[i][j-1] + p3*dp[i-1][j-1];
ZOJ 3380
可以dp处理有没有i个位置的数字一样的概率dp[i][j]表示当前已经放了j个位置，用到了第i种颜色
即dp[i][j]=dp[i-1][j-k]*C(m-(j-k),k) (k<=j&&k<l) 表示我们找出k个位置填入数字i
因为如果l>m则必然是无解的，l>m/2可以直接用组合计数算出，时间减少一半数字很大，也没有取模，需要大数处理
一个简易的入门：点击打开链接
kuangbin的总结：点击打开链接
我搞的题目：点击打开链接
前段时间一直在做概率的题目。
一、期望
其中求解期望问题刚开始一直不理解。后来做得多了有感觉。
例：（有放回）
在5件产品有4件正品，1件次品，从中任取2件，记其中含正品的个数个数为随机变量ξ，则ξ的数学期望Eξ是 1.6
在5件产品有4件正品，1件次品，从中任取2件，记其中含正品的个数个数为随机变量ξ，则ξ=2时所取次数的数学期望是1.16
第一个例子是平常学的期望，做一件事情各个结果的可能情况期望。第二个例子是题目出的，做一件事情需要次数的期望。
解决这类问题，对随机变量A、B,有 数学期望E(aA+bB)=aE(A)+bE(b);
有了这个公式你就可以进行将连续的期望问题，转化为独立的状态了，概率就相当于a，b；A，B为变量。变为线性问题。
E1=（1/3）*E1+（1/3）*E2+（1/3）*E3+1 ①
表示 下一次可以走到2或者3或在原地1，每个可能概率是1/3 ,注意是下一次，故要加上1.
对于这类问题有三种，
1 无环直接递推解决，概率DP求期望入门，HDU 4405，POj 2096,HDU 3853
zoj 3640 当终结点不容易确定的时候用记忆化搜索。
2 只是个别点会构成回路 hdu4035 zoj3329
既DP[i]可能由DP[i+k]和DP[i+j]需要求的比如DP[0]决定
相当于概率一直递推下去会回到原点
比如
(1):DP[i]=a*DP[i+k]+b*DP[0]+d*DP[i+j]+c;
但是DP[i+k]和DP[0]都是未知
这时候根据DP[i]的方程式假设一个方程式：
比如:
(2):DP[i]=A[i]*DP[i+k]+B[i]*DP[0]+C[i];
因为要求DP[0],所以当i=0的时候但是A[0],B[0],C[0]未知
对比(1)和(2)的差别
这时候对比(1)和(2)发现两者之间的差别在于DP[i+j]
所以根据(2)求DP[i+j]然后代入(1)消除然后对比(2)就可以得到A[i],B[i],C[i]
然后视具体情况根据A[i],B[i],C[i]求得A[0],B[0],C[0]继而求DP[0]
3 高斯消元解决.......HDU2262 HDU4418
这个没什么说的
4 状态压缩 HDU4336 这个和无环递推一样，不过也可以用容斥的方法。
首先容斥定理相当于是求多个集合的并集，但是因为两两之间有交集所以需要剪掉重复剪掉的部分。当集合个数多于三个的时候又会出现三个集合之间的交集被误剪掉了，或者四个之间的交集部分又重复计算了等等。于是容斥定理就有用了，当集合个数为n时，我们要算总并集，我们就要算所有的一个集合的大小，所有的两个集合的交集的大小，所有的三个的集合交集的大小，直到n个集合的交集的大小，中间偶数个减掉，奇数个加起来就可以了。楼主容斥定理的那个程序用i的二进制表示一个大集合，i中的每个1表示一个小集合。当i++从0到(1<<n-1)就是00...000到11...111变化的过程可以穷举所有的可能交集情况，然后算出它的大小。“cnt&1”就是在判断奇偶，通过加或者减算出并集。
“1.0/sum”是在算包数，就是期望=np，所以n=期望除以概率，这里期望只要是1就可以了。然后就是每种情况求概率的问题了，比如说某种情况是1101，那么就是算1000,0100,0001三种事件同时发生的概率，因为各个事件是独立的，所以直接可以把概率相加得到总的概率。
独立事件概率相加理解：一次取到这几个东西都行的概率。而之前单个概率值是取单个的概率
其中 f[i]+=in[j]*f[i|(1<<j)];可以保证无后向性。
二、概率
poj3744 一条路上有地雷，一个人要通过那必然是都得通过（没有踩到），递推就能解决。使用要矩阵快速幂。注意移位使用本来的数字否则会溢出。
poj3071 足球概率模拟题，注意二进制倍增的过程中三层循环。
CodeForces 148D dp意思是龙在X X情况下胜利的概率，依据题意可以很容易写出。
poj2151 每队均至少做一题的概率P1 减去 每队做题数均在1到N-1之间的概率P2
SGU 495
题意：n个盒子里装有礼物，m个人随机选择礼物，选完之后空盒子放回
问选中的礼物数的期望。
m个人是独立的。
对于每个礼物不被人选中的概率为((n-1)/n)^m
那么不被选中的礼物数的期望就是 n*((n-1)/n)^m
所以答案就是 n-n*((n-1)/n)^m;HDU 4089 dp[i][j]表示队列中有i个人，Tomato排在第j个，能发生所求事件的概率。
转移的时候，考虑的是队头的那个人而不是当前在J这个位置。
j == 1 : dp[i][1] = p1*dp[i][1] + p2*dp[i][i] + p4;
2<=j<=k: dp[i][j] = p1*dp[i][j] + p2*dp[i][j-1] + p3*dp[i-1][j-1] + p4;
j > k : dp[i][j] = p1*dp[i][j] + p2*dp[i][j-1] + p3*dp[i-1][j-1];
ZOJ 3380
可以dp处理有没有i个位置的数字一样的概率dp[i][j]表示当前已经放了j个位置，用到了第i种颜色
即dp[i][j]=dp[i-1][j-k]*C(m-(j-k),k) (k<=j&&k<l) 表示我们找出k个位置填入数字i
因为如果l>m则必然是无解的，l>m/2可以直接用组合计数算出，时间减少一半数字很大，也没有取模，需要大数处理
ACM 中的期望，概率 问题