概率dp
首先是正着递推的计算概率的dp问题
https://ac.nowcoder.com/acm/contest/28263/A
纯数学题
对随机的数字大小分类讨论，计算概率的时候利用高中几何概型的线性规划手法进行计算。
double g=0.5;
void solve(){
double k,x;cin>>k>>x;
double ans=0;
if(k==x)ans=g;
else if(k>=2*x)ans=0;
else if(k<x){
ans=g*(x*x-k*k);
ans/=x*x;
ans+=g;
}
else {
ans=g*(2*x-k)*(2*x-k);
ans/=x*x;;
}
baoliu(ans,2);
cout<<endl;
}
CF148D Bag of mice
状态：\(f[i][j]\)表示袋中有i只白鼠j只黑鼠时，A获胜的概率
起点：\(f[0][i]=0，f[i][0]=1\)
终点：\(f[w][b]\)
转移：
1.先手拿到白鼠：\(f[i][j]+=i/(i+j)\)
2.先手黑鼠，后手白鼠：\(f[i][j]+=0,\) 这种情况不用处理
3.先手黑鼠，后手黑鼠，跑白鼠：\(f[i][j]+=j/(i+j) *(j-1)/(i+j-1) *i/(i+j-2) *f[i-1][j-2]\)
4.先手黑鼠，后手黑鼠，跑黑鼠：\(f[i][j]+=j/(i+j) *(j-1)/(i+j-1) *(j-2)/(i+j-2) *f[i][j-3]\)
int n, m;
int a[N];
//两个人各操作一次为1轮
double f[N][N];
void solve(){
cin>>n>>m;
for(int i=1;i<=n;i++){
f[i][0]=1;
}
for(int i=1;i<=m;i++){
f[0][i]=0;
}
for(int i=1;i<=n;i+=1.0){
for(int j=1;j<=m;j+=1.0){
f[i][j]+=(double)i/(i+j);
if(i>=1 && j>=2)
f[i][j]+=f[i-1][j-2]*(double)j*(j-1)*(i)/(double)((i+j)*(i+j-1)*(i+j-2));
if(j>=3)
f[i][j]+=f[i][j-3]*(double)j*(j-1)*(j-2)/(double)((i+j)*(i+j-1)*(i+j-2));
//cerr<<f[i][j]<<" ";
}
}
baoliu(f[n][m],9);
}
题意：有2^n支球队比赛，每次和相邻的球队踢，两两淘汰，给定任意两支球队相互踢赢的概率，求最后哪只球队最可能夺冠
Solution：考虑\(f[i][j]\)是第i次大混战编号为j的队伍获胜的概率，考虑转移需要找到本轮的对手，并调用其获胜的概率。由于n范围很小，直接暴力枚举即可。核心问题是如何找到合法可能的对手，我们观察后利用位运算得到。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define baoliu(x,y) cout<<fixed<<setprecision(y)<<x;
const int N=130;
double w[N][N];
double f[8][N];
//f[i][j]:第i场，第j队win的概率
int main(){
int n;
//从0下标开始才能在后续进行高效位运算
while(cin>>n,n!=-1){
//对于这种多测也考虑写成solve函数，忘清空了
int m=1<<n;
memset(f,0,sizeof f);
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
cin>>w[i][j];
}
}
for(int i=0;i<m;i++)f[0][i]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++){
for(int k=0;k<m;k++){
if(((j>>(i-1))^1)==(k>>(i-1))){
//所有情况的获胜概率是累加的
f[i][j]+=f[i-1][j]*f[i-1][k]*w[j][k];
}
}
}
}
double mx=0;int pos=0;
for(int i=0;i<m;i++){
if(mx<f[n][i]){
mx=f[n][i];
pos=i;
}
}
//仔细读题发现，队伍编号从1开始，而我从0开始是为利用位运算
cout<<pos+1<<endl;
}
}
[CF768D Jon and Orbs](https://www.luogu.com.cn/problem/CF768D
题面翻译
有k件物品，每天随机出现一件。设每种球都出现至少一次以上为事件U.
求最小天数使得U发生的概率不小于\(\frac{p}{2000}\)，有 \(q\) 组询问，每组询问给定这个 \(p\)。