题目描述
一个软件有 \(s\) 个子系统，会产生 \(n\) 种 bug。
某人一天发现一个 bug，这个 bug 属于某种 bug，发生在某个子系统中。
求找到所有的 \(n\) 种 bug，且每个子系统都找到 bug，这样所要的天数的期望。
bug 的数量是无穷大的，所以发现一个 bug，出现在某个子系统的概率是 \(\dfrac{1}{s}\)，属于某种类型的概率是 \(\dfrac{1}{n}\)。
问发现 \(n\) 种 bug，每个子系统都发现 bug 的天数的期望。
输入格式
输入数据的第一行为两个整数 \(n\) 和 \(s\)。
输出格式
输出每个子系统都发现 bug 的天数的期望（保留四位小数）
输入输出样例
输入 #1
1 2
输出 #2
3.0000
思路：
期望的套路公式：
设 \(w_1\) 为在 \(p\) 概率下成功所获得对期望的贡献，\(w_2\) 为在 \(p\) 概率下失败所获得对期望的贡献，则对于 \(f\) 期望有：
\[f=w_1 \times p + w_2 \times (1-p)
\]
但 \(w_1\) 和 \(w_2\) 有诸多变种，使期望令人望而却步。
比如这一基础题，可以设 \(f_{i,j}\) 为发现 \(i\) 种 bug出现在 \(j\) 个子系统的天数的期望。那么依照套路而言，我们会有以下的状态转移方程：
\[f_{i,j}=f_{i,j} \times \dfrac{i}{n} \times \dfrac{j}{s} + f_{i+1,j} \times \dfrac{n-i}{n} \times \dfrac{j}{s} + f_{i,j+1} \times \dfrac{i}{n} \times \dfrac{s-j}{s} + f_{i+1,j+1} \times \dfrac{n-i}{n} \times \dfrac{s-j}{s}+1
\]
其中这个 \(+1\) 需要读者理解。这里的 \(+1\) 是在满足条件的情况下达到左式的条件。有时这个 \(+1\) 可能不止是一个数字，也可能带有概率，需要读者具体题目具体分析。
但上式不能直接用，因为我们可以发现等号左右两侧都有 \(f_{i,j}\) 的关系式，需要进行转化：
\[f_{i,j} \times (1-\dfrac{i}{n} \times \dfrac{j}{s})=f_{i+1,j} \times \dfrac{n-i}{n} \times \dfrac{j}{s} + f_{i,j+1} \times \dfrac{i}{n} \times \dfrac{s-j}{s} + f_{i+1,j+1} \times \dfrac{n-i}{n} \times \dfrac{s-j}{s}+1
\]
\[f_{i,j}=\dfrac{f_{i+1,j} \times \dfrac{n-i}{n} \times \dfrac{j}{s} + f_{i,j+1} \times \dfrac{i}{n} \times \dfrac{s-j}{s} + f_{i+1,j+1} \times \dfrac{n-i}{n} \times \dfrac{s-j}{s}+1}{1-\dfrac{i}{n} \times \dfrac{j}{s}}
\]
\[f_{i,j}=\dfrac{f_{i+1,j} \times (n-i) \times j + f_{i,j+1} \times i \times (s-j) + f_{i+1,j+1} \times (n-i) \times (s-j)+n \times s}{n\times s-i \times j}
\]
这样就可以用了。
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define TP template<typename T>
#define TP_ template<typename T,typename ... T_>
TP void read(T &x)
{
x=0;int f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
x*=f;
}
TP_ void read(T &x,T_&...y){read(x);read(y...);}
TP void write(T x){if(x<0){putchar('-'),x=-x;}if(x>9)write(x/10);putchar(48+x%10);}
TP void writeln(const T x){write(x);puts("");}
TP void writesp(const T x){write(x);putchar(' ');}
TP_ void writeln(const T x,T_ ...y){writesp(x);writeln(y...);}
using LL=long long;
constexpr int N=1e3+5;
double f[N][N];
double n,s;
int main()
{
scanf("%lf%lf",&n,&s);
for(int i=n;i>=0;--i)
for(int j=s;j>=0;--j)
{
if(i==n&&j==s)continue;
double sum=0;
sum+=f[i+1][j]*(n-i)*j;
sum+=f[i][j+1]*i*(s-j);
sum+=f[i+1][j+1]*(n-i)*(s-j);
f[i][j]=(sum+n*s)/(n*s-i*j);
}
printf("%.4lf\n",f[0][0]);
return 0;
}