题目描述
有 n 盏红灯，m 盏绿灯，每次随机熄灭一盏，直到一种颜色的灯全部被熄灭，求剩下灯个数的期望。
输入格式
两个整数 n 和 m，分别表示红灯个数和绿灯个数。
输出格式
一个小数，四舍五入保留六位小数。
样例
样例输入
10 20
样例输出
2.294372
感谢wwppcc的推导%%%%%%
一道究极煞笔的数论题
数据范围1e9，很显然不能dp，但dp仍能得部分分
DP暴力
实际上，根据"直到一种颜色的灯全部被熄灭"可以看出，如果不限数据范围，这一道实际是red is good的变形，不同的是它有两个初始状态，但没有终止（或者说，是dp的边界），因此可以直接转移：
\(f[i][j]=f[i-1][j]*\frac{i}{i+j}+f[i][j-1]*\frac{j}{i+j}\)
\(f[i][0]=i\)
\(f[0][j]=j\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=5001;
double f[N][N];
int n,m;
int main(){
cin>>n>>m;
for(int j=1;j<=m;j++) f[0][j]=j;
for(int i=1;i<=n;i++) f[i][0]=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=f[i-1][j]*i/(i+j)+f[i][j-1]*j/(i+j);
}
}
cout<<setprecision(6)<<fixed<<f[n][m]<<endl;
}
推式子
n个红，m个绿，我们先假设：
最后一个是红，那么前面拿走的一定是绿（因为仅同一颜色的就立马停止）
那么先考虑红的期望：
红的总情况为：\(C^{n}_{m+n}\)
剩一个的（因为已经有一红一绿固定了）：\(C^{n-1}_{n+m-2}\)
那么剩两个的：\(C^{n-2}_{n+m-3}\)
剩n个的：\(C^{n-n}_{n+m-n-1}\)
那么对于红的期望，则有：
\(\frac{1*C^{n-1}_{n+m-2}+2*C^{n-2}_{n+m-3}+…………+n*C^{n-n}_{n+m-n-1}}{C^{n}_{n+m}}\)
（以防看不清）
开始化简
我们可以给分子的每一项都提个1，即：
\(C^{n-1}_{n+m-2}+C^{n-2}_{n+m-3}+…………+C^{n-n}_{n+m-n-1}+(2-1)*C^{n-2}_{n+m-3}+…………\)
剩n-1个的：\(C^{n-n+1}_{n+m-n}\)
即\(C^{1}_{m+n-n}\)
因为\(C^{0}_{n+m-n-1}=C^{0}_{n+m-n}=1\)
那么我们可以考虑将第n项和n-1项合并，利用公式\(C^m_{n+1}=C^m_n+C^{m-1}_n\)得：
\(C^{1}_{n+m-n}+C^{0}_{n+m-n}=C^{1}_{n+m-n+1}\)
又知n-2项为：\(C^{n-n+2}_{n+m-n+1}\)
即：\(C^{2}_{n+m-n+1}\)
而它又可以和合并的那一项接着合并，那么对于提1的式子会有：
\(C^{n-1}_{n+m-2}+C^{n-2}_{n+m-3}+…………+C^{n-n}_{n+m-n-1}=C^{n-1}_{n+m-1}\)
而原分子还剩下:
\(C^{n-2}_{n+m-3}+2*C^{n-3}_{n+m-4}+…………+(n-1)*C^{n-n}_{n+m-n-1}\)
那么考虑给剩下的项接着提1合并，最后整个分子为：
\(C^{n-1}_{n+m-1}+C^{n-2}_{n+m-2}+…………+C^{n-n}_{n+m-n}\)
很显然，他们仍可以根据\(C^m_{n+1}=C^m_n+C^{m-1}_n\)合并，得：
\(C^{n-1}_{n+m}\)
那么对于红色的期望值则会有：
\(\frac{C^{n-1}_{n+m}}{C^{n}_{n+m}}\)
根据公式\(C^m_n=\frac{n!}{m!(n-m)!}\)可得：
\({C^{n-1}_{n+m}}=\frac{(n+m)!}{(n-1)![n+m-(n-1)]!}\)
即：\(\frac{(n+m)!}{(n-1)!(m+1)!}\)
\(C^{n}_{n+m}=\frac{(n+m)!}{n!(n+m-n)!}\)
即：\(\frac{(n+m)!}{n!m!}\)
两个值做比，可得：
\(\frac{n!m!}{(n-1)!(m+1)!}\)
展开，约分，最后得：
\(\frac{n}{m+1}\)
绿色的话将n和m对调一下即可，结果是：
\(\frac{m}{n+1}\)
因此将两个结果加和就是答案
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
double ans;
int main(){
cin>>n>>m;
ans=(double)n/(m+1)+(double)m/(n+1);
cout<<setprecision(6)<<fixed<<ans<<endl;
}