题意：有\(k\)种苹果和\(n\)个箱子，每个箱子中有一些苹果，先等概率选取\(n\)个箱子组成集合的非空子集，再从选出的苹果中随机选一个，问每种苹果被选中的概率是多少
箱子\(i\)有\(a_{i,j}\)个第\(j\)种苹果，第\(i\)个箱子的总苹果数\(siz_i=\sum\limits_{j=1}^ka_{i,j}\)，苹果总数\(sum=\sum\limits_{i=1}^n siz_i\)
每个箱子中的苹果被选中的概率是相同的，所以先考虑选箱子，设\(f_{i,j}\)表示在前\(i\)个箱子中选\(j\)个苹果的方案数（只能一箱一箱选），那么\(f_{i,j}=f_{i-1,j}+f_{i-1,j-siz_i}\)
再设\(g_{i,j}\)表示在所有不是\(i\)的箱子中选\(j\)个苹果的方案数，那么\(g_{i,j}=f_{n,j}-g_{i,j-siz_i}\)
于是，选中了箱子\(i\)的情况对箱子\(i\)中每个苹果被选中的概率贡献为\(\sum\limits_{j=0}^{sum-siz_i}\frac{g_{i,j}}{2^n-1}\times\frac{1}{j+siz_i}\)
解释一下
\(f\) 的递推显然。
\(g\) 的递推看似很神奇，其实移项后可以发现 \(g_{i,j}+g_{i,j-siz_i}=f_{n,j}\)，也就是 \(f_{n,j}\) 的递推，当不选第 \(i\) 个箱子时方案数为 \(g_{i,j}\)，反之即为选第 \(i\) 个箱子里的 \(siz_i\) 个苹果，那么方案数为其他箱子选 \(j-siz_i\) 个苹果的方案数，也就是 \(g_{i,j}\)。
计算答案时，枚举到 \(i\)，是已经假设箱子 \(i\) 被选中后的；枚举 \(j\) 表示其他箱子里的苹果数，从其他箱子里选出 \(j\) 个苹果的方案数为 \(g_{i,j}\)，对于选出的任意子集，其概率为 \(\frac{g_{i,j}}{2^n-1}\)，在选出来的所有苹果中，每一个苹果被选中的概率为 \(\frac{1}{j+siz_i}\)。
不知道为什么本题不压维过不了。
#include <bits/stdc++.h>
using namespace std;
#define srand srand(time(NULL))
#define random(x) rand() % (x)
#define il inline
#define ptc putchar
#define reg register
#define mp make_pair
#define pb push_back
#define R(i, l, r) for (int i = l; i <= r; ++i)
#define debug puts("--------------------------------------------")
typedef long long ll;
typedef pair<int, int> PII;
namespace kunkun
{
template <typename T>
il void read(T &x)
{
x = 0; T f = 1; char ch;
while (!isdigit(ch = getchar())) f -= (ch == '-') << 1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch & 15), ch = getchar(); x *= f;
}
template <typename T, typename ...L>
il void read(T &x, L &...y) {read(x); read(y...);}
template <typename T>
il void write(T x)
{
if (x < 0) ptc('-'), x = -x;
if (x > 9) write(x / 10);
ptc(x % 10 + '0');
}
template <typename T, typename ...L>
il void write(T &x, L &...y) {write(x), ptc(' '); write(y...);}
}
using namespace kunkun;
const int N = 55;
// O(50*50*50*200)
int n, k, a[N][N], siz[N], sum;
ll f[500005], g[500005];
class RandomApple
{
public:
vector <double> theProbability(vector <string> hundred, vector <string> ten, vector <string> one)
{
n = hundred.size();
k = hundred[0].size();
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= k; ++j)
{
a[i][j] = (hundred[i - 1][j - 1] - '0') * 100 + (ten[i - 1][j - 1] - '0') * 10 + one[i - 1][j - 1] - '0';
siz[i] += a[i][j];
}
sum += siz[i];
}
// cout << "sum: " << sum << endl;
vector <double> ans;
R(i, 1, k) ans.pb(0);
// 设f[i][j]表示在前i个箱子中选j个苹果的方案数
f[0] = 1;
// f[1][siz[1]] = 1;
for (int i = 1; i <= n; ++i)
{
for (int j = sum; j >= siz[i]; --j) f[j] += f[j - siz[i]];
// for (int j = 0; j <= sum; ++j)
// {
// f[i][j] = f[i - 1][j];
// if (j >= siz[i]) f[i][j] += f[i - 1][j - siz[i]];
// }
}
for (int i = 1; i <= n; ++i)
{
long double tmp = 0;
for (int j = 0; j <= sum; ++j)
{
// cout << i << ' ' << j << endl;
g[j] = f[j];
if (j >= siz[i]) g[j] -= g[j - siz[i]];
if (j + siz[i] <= sum) tmp += g[j] * 1.0 / (j + siz[i]);
}
tmp /= ((long double)pow(2, n) - 1);
for (int j = 1; j <= k; ++j)
{
ans[j - 1] += tmp * a[i][j];
// 选到箱子i中任意一个苹果的概率为tmp
}
// cout << "???\n";
}
// debug;
return ans;
}
} ;
/*
signed main()
{
vector <string> h, t, o;
h.pb("01010110"), h.pb("00011000"), h.pb("00001000"), h.pb("10001010"), h.pb("10111110");
t.pb("22218214"), t.pb("32244284"), t.pb("68402430"), t.pb("18140323"), t.pb("29043145");
o.pb("87688689"), o.pb("36101317"), o.pb("69474068"), o.pb("29337374"), o.pb("87255881");
// h.pb("10");
// t.pb("00");
// o.pb("00");
// h.pb("0000"), h.pb("0000"), h.pb("0000");
// t.pb("2284"), t.pb("0966"), t.pb("9334");
// o.pb("1090"), o.pb("3942"), o.pb("4336");
// h.pb("00"), h.pb("00");
// t.pb("00"), t.pb("00");
// o.pb("21"), o.pb("11");
// debug;
vector <double> ans = solver.theProbability(h, t, o);
for (auto x : ans) printf("%.10f ", x);
return 0;
}
//*/