class Solution {
public:
double getProbability(vector<int>& balls) {
}
};
1467. 两个盒子中球的颜色数相同的概率
桌面上有 2n 个颜色不完全相同的球，球上的颜色共有 k 种。给你一个大小为 k 的整数数组 balls ，其中 balls[i] 是颜色为 i 的球的数量。
所有的球都已经 随机打乱顺序 ，前 n 个球放入第一个盒子，后 n 个球放入另一个盒子（请认真阅读示例 2 的解释部分）。
注意：这两个盒子是不同的。例如，两个球颜色分别为 a 和 b，盒子分别为 [] 和 ()，那么 [a] (b) 和 [b] (a) 这两种分配方式是不同的（请认真阅读示例的解释部分）。
请返回「两个盒子中球的颜色数相同」的情况的概率。答案与真实值误差在 10^-5 以内，则被视为正确答案
示例 1：
输入：balls = [1,1] 输出：1.00000 解释：球平均分配的方式只有两种： - 颜色为 1 的球放入第一个盒子，颜色为 2 的球放入第二个盒子 - 颜色为 2 的球放入第一个盒子，颜色为 1 的球放入第二个盒子 这两种分配，两个盒子中球的颜色数都相同。所以概率为 2/2 = 1 。
示例 2：
输入：balls = [2,1,1] 输出：0.66667 解释：球的列表为 [1, 1, 2, 3] 随机打乱，得到 12 种等概率的不同打乱方案，每种方案概率为 1/12 ： [1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1] 然后，我们将前两个球放入第一个盒子，后两个球放入第二个盒子。 这 12 种可能的随机打乱方式中的 8 种满足「两个盒子中球的颜色数相同」。 概率 = 8/12 = 0.66667
示例 3：
输入：balls = [1,2,1,2] 输出：0.60000 解释：球的列表为 [1, 2, 2, 3, 4, 4]。要想显示所有 180 种随机打乱方案是很难的，但只检查「两个盒子中球的颜色数相同」的 108 种情况是比较容易的。 概率 = 108 / 180 = 0.6 。
提示：
1 <= balls.length <= 81 <= balls[i] <= 6sum(balls) 是偶数原站题解
java 解法, 执行用时: 2 ms, 内存消耗: 38.9 MB, 提交时间: 2023-09-21 10:13:49
class Solution {
public double getProbability(int[] balls) {
int n = balls.length;
int sum = 0;
double ans = 0;
for (int ball: balls) {
sum += ball;
}
// 阶乘初始化
double[] fac = new double[sum + 1];
fac[0] = 1;
for (int i = 1; i <= sum; i++)
fac[i] = fac[i - 1] * i;
sum >>= 1;
/* dp数组初始化
dp数组解释：dp[i][j][k]:表示在第i个颜色球时，选择的k个球的与未选择的球的颜色差为j时的方案数，
此时未考虑k个球的内部排序，且j可能为负数，所以整体偏移了n+1个单位。
*/
double[][][] dp = new double[n + 1][2 * n + 3][sum + 1];
dp[0][n + 1][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= balls[i - 1]; j++) {
for (int k = j; k <= sum; k++) {
for (int r = 1; r < 2 * n + 2; r++) {
if (j == 0) {
dp[i][r - 1][k] += dp[i - 1][r][k];
} else if (j == balls[i - 1]) {
dp[i][r + 1][k] += dp[i - 1][r][k - j];
} else {
dp[i][r][k] += dp[i - 1][r][k - j] * fac[balls[i - 1]] / fac[balls[i - 1] - j] / fac[j];
}
}
}
}
}
//将前n个球和后n个球的内部顺序加上
ans = dp[n][n + 1][sum] * fac[sum] * fac[sum];
//除以总的可能数
for (int i = 1; i <= sum * 2; i++) {
ans /= i;
}
return ans;
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-09-21 10:13:01
/**
* dp[i][j][p][q] 表示选完前i种球后，第一个盒子选了j个球，第一个盒子的颜色数为p,
* 第二个盒子的颜色数为q的方案数。 状态转移， 每次选第i种球时， 有三种转移。
* 1.全给第一个盒子
* 2.全给第二个盒子
* 3.两个盒子都分到了这种颜色的球(枚举一下分到球的个数)
* fn是计算n个球的排列方案数为base的情况下， 另外加入m个相同颜色球后排列的方案数。
*/
func getProbability(balls []int) float64 {
dp := [9][49][9][9]float64{}
dp[0][0][0][0] = 1
fn := func(base float64, n, m int) float64{
if base == 0{
return 0
}
for i := 1;i <= m;i++{
base = base * float64(n + i) / float64(i)
}
return base
}
var midSum int
var totalCount = float64(1)
for _, b := range balls{
totalCount = fn(totalCount, midSum, b)
midSum += b
}
midSum /= 2
var preSum int
for i := 0;i < len(balls); i++{
for j := 0;j <= midSum; j++{
for p := 0; p < len(balls); p++{
for q := 0; q < len(balls); q++{
for n := 1;n < balls[i]; n++{
if j + n <= midSum && preSum - j + balls[i] - n <= midSum{
dp[i + 1][j + n][p + 1][q + 1] += fn(fn(dp[i][j][p][q], j, n), preSum - j, balls[i] - n)
}
}
if j + balls[i] <= midSum && preSum - j <= midSum{
dp[i + 1][j + balls[i]][p + 1][q] += fn(dp[i][j][p][q], j, balls[i])
}
if preSum - j + balls[i] <= midSum{
dp[i + 1][j][p][q + 1] += fn(dp[i][j][p][q], preSum - j, balls[i])
}
}
}
}
preSum += balls[i]
}
var matchCount float64
for kind := 0; kind <= len(balls); kind++{
matchCount += dp[len(balls)][midSum][kind][kind]
}
return matchCount / totalCount
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 7.2 MB, 提交时间: 2023-09-21 10:11:14
/**
* 题目问的是，n个球已经等分到2个盒子的情况下，使得2个盒子里面的颜色数相等。
* 首先，n个球等分到2个盒子的概率P1=C(n,2n)/(2^n) 然后，
* n个球等分到2个盒子且2个盒子里面颜色数相同的概率，可以用dp计算：dp[n][ndiff][diff]代表，
* 从第n种球开始考虑，两个盒子里面的球数差距为ndiff，颜色差距为diff时的概率，
* 则有如下转移方程： dp[i][ndiff][diff] = sum(C(balls[i], j) / (2^balls[i]) * dp[i+1][j-k][!!j-!!k] for j+k=balls[i])
* 最后运用条件概率公式，所求为在 n个球等分到2个盒子 的前提下 n个球等分到2个盒子且2个盒子里面颜色数相同的概率，
* 则答案为dp求得的概率除以等分到2个盒子的概率
*/
class Solution {
public:
double solve(vector<map<pair<int, int>, double>>& memo, vector<int>& balls, int i, int ndiff, int diff) {
if (i == balls.size())
return diff == 0 && ndiff == 0;
if (memo[i].find({ndiff, diff}) != memo[i].end()) return memo[i][{ndiff, diff}];
double& ans = memo[i][{ndiff, diff}];
ans = 0;
double all = 1;
for (int j = 0; j <= balls[i]; j++) {
int k = balls[i] - j;
int dndiff = j - k;
int ddiff = (!!j) - (!!k);
ans += C(balls[i], j) / pow(2.0, balls[i]) * solve(memo, balls, i+1, ndiff+dndiff, diff+ddiff);
}
return ans;
}
double getProbability(vector<int>& balls) {
vector<map<pair<int, int>, double>> memo(balls.size());
double p = solve(memo, balls, 0, 0, 0);
int s = 0;
for (int j = 0; j < balls.size(); j++)
s += balls[j];
return p / (C(s, s/2) / pow(2.0, s));
}
double fact(int n) {
if (!n) return 1;
return fact(n-1) * n;
}
double A(int n, int m) {
return fact(n) / fact(n-m);
}
double C(int n, int m) {
return fact(n) / fact(n-m) / fact(m);
}
};
python3 解法, 执行用时: 1888 ms, 内存消耗: 683 MB, 提交时间: 2023-09-21 10:09:53
class Solution:
def multinomial(self, n: List[int]) -> float:
return factorial(sum(n))/prod([factorial(i) for i in n])
# 暴力数学求解
def getProbability(self, balls: List[int]) -> float:
print(self.multinomial([1,2,3]))
k, n, Q = len(balls), sum(balls)// 2, 0
arrays = [range(0,i+1) for i in balls]
t = list(product(*arrays))
for i in range(len(t)):
if sum(t[i]) == n and t[i].count(0) == t[-i-1].count(0):
Q += self.multinomial(t[i]) * self.multinomial(t[-i-1])
return Q / self.multinomial(list(balls))