题意分析

Ivan 在收集软件漏洞时，将漏洞分为 $n$ 类，并且程序有 $s$ 个子组件。每天他会发现一个漏洞，该漏洞属于某一类并出现在某一子组件中，且每个漏洞的类别和子组件是独立且均匀分布的。当满足以下两个条件时，程序被称为“令人作呕”：

1. 每个漏洞类别中至少发现一个漏洞。
2. 每个子组件中至少发现一个漏洞。

我们需要计算 Ivan 达到这一条件所需的期望天数。

解题思路

这是一个典型的期望动态规划问题，类似于“Coupon Collector Problem”的扩展。我们需要计算覆盖所有类别和子组件的期望时间。

设 $dp[i][j]$ 表示已经覆盖了 $i$ 个漏洞类别和 $j$ 个子组件时，还需要多少天才能满足条件。初始状态是 $dp[n][s] = 0$，因为已经满足条件时不需要额外天数。

状态转移方程如下：

• 新漏洞的类别未被覆盖（概率为 $\frac{n-i}{n}$），子组件未被覆盖（概率为 $\frac{s-j}{s}$），此时转移到 $dp[i+1][j+1]$。
• 新漏洞的类别已被覆盖（概率为 $\frac{i}{n}$），子组件未被覆盖（概率为 $\frac{s-j}{s}$），此时转移到 $dp[i][j+1]$。
• 新漏洞的类别未被覆盖（概率为 $\frac{n-i}{n}$），子组件已被覆盖（概率为 $\frac{j}{s}$），此时转移到 $dp[i+1][j]$。
• 新漏洞的类别和子组件均已被覆盖（概率为 $\frac{i}{n} \times \frac{j}{s}$），此时不改变状态。

因此，状态转移方程为：

$$dp[i][j] = 1 + \frac{(n-i)(s-j)}{n s} dp[i+1][j+1] + \frac{i(s-j)}{n s} dp[i][j+1] + \frac{(n-i)j}{n s} dp[i+1][j] $$

然后解这个方程：

$$dp[i][j] = \frac{1 + \frac{(n-i)(s-j)}{n s} dp[i+1][j+1] + \frac{i(s-j)}{n s} dp[i][j+1] + \frac{(n-i)j}{n s} dp[i+1][j]}{1 - \frac{i j}{n s}} $$

标程

#include<bits/stdc++.h>
using namespace std;
#define per(i,a,b) for(int i=a;i <= b;i++)
#define max(a,b) a=max(a,b)
#define min(a,b) a=min(a,b)
#define sz(x) (int)x.size()
typedef long long ll;
ll gcd(ll a,ll b){while(b){ll t=b;b=a%b;a=t;}return a;}
const int inf=0x3f3f3f3f;
const int mod=1000000007;
#define siz 1005
int n,s;
double dp[siz][siz];

int main()
{
	scanf("%d%d",&n,&s);
	dp[n][s]=0.0;
	for(int i=n;i>=0;i--){
		for(int j=s;j>=0;j--){
			if(i==n&&j==s)continue;
			dp[i][j]=(n*s+(n-i)*j*dp[i+1][j]+i*(s-j)*dp[i][j+1]+(n-i)*(s-j)*dp[i+1][j+1])/(n*s-i*j);
		}
	}
	printf("%.4f\n",dp[0][0]);
	return 0;
}