题解：P4204 [NOI2006] 神奇口袋

题意：口袋里有 \(t\) 种球，每种球初始有 \(a_i\) 个，每次从其中随机拿一个球并放回，同时再放入 \(d\) 个和拿出来球同种颜色的球。现在给出若干对 \((x_i,y_i)\)，问同时满足第 \(x_i\) 次操作摸出来 \(y_i\) 这一颜色的球的总概率。

做法：

首先我们会证明一个结论：对于 \((1,y_1),(2,y_2),\cdots (n,y_n)\)，我们可以随意重排 \(y\)。

这个比较显然，假设第 \(i\) 种球在 \(y\) 中出现 \(cnt_i\) 次，记 \(s=\sum a_i\)，那么总概率为：

\[\frac{\prod\limits_{i=1}^t\prod\limits_{j=0}^{cnt_i-1}(a_i+jd)}{\prod\limits_{i=0}^{n-1}(s+id)} \]

显然这个东西和 \(y\) 的顺序无关，只和 \(cnt\) 有关，所以随意重排都是这个概率。

然后我们可以用这个结论去证明下面这个结论：对于 \((x_1,y_1),(x_2,y_2),\cdots (x_n,y_n)\)，我们可以把 \(x\) 离散成 \(1,2,\cdots n\)，概率不变。

因为我们上面有一个对于 \(x\) 是 \(1,2,\cdots n\) 的结论，我们要往这个形式靠，考虑把下面直接补成 \(1,2,\cdots x_n\)，然后对于没有强行要求的位置，我们枚举这个位置放了什么。

举个例子，比如我原本有 \((1,3),(3,4)\) 这两个对，因为 \((2, ?)\) 少了，我们直接补上并枚举 \(?\) 是哪种球。

显然这个东西的结果和原本要求的概率并不改变。

那么因为第一个结论，我们可以直接把 \(y_1,y_2,\cdots y_n\) 拉到最前面 \(n\) 个。注意到这个时候后面枚举的仍然是剩下的所有情况，所以概率仍然不变，或者说逆用全排列公式，可以得到概率等于 \((1,y_1),(2,y_2)\cdots (n,y_n)\)。

有了这个结论直接去做就可以了，实现上需要高精度，但是直接开乘除法太慢了，因为数据范围不大，可以直接分解质因数先约，最后乘起来即可。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e4 + 5, N = 4e4;
int t, n, d, a[maxn], prime[maxn], vis[maxn], tot, lpf[maxn];
void prepare() {vis[1] = vis[0] = 1;for (int i = 2; i <= N; i++) {if(!vis[i])prime[++tot] = i, lpf[i] = tot;for (int j = 1; j <= tot && prime[j] * i <= N; j++) {vis[i * prime[j]] = 1;lpf[i * prime[j]] = j;if(i % prime[j] == 0) break;}}
}
int num[maxn];
void add(int x, int v) {while(x != 1) {num[lpf[x]] += v;x /= prime[lpf[x]];}
}
struct Bigint {vector<int> a;Bigint() {a.resize(1); a[0] = 1;}int size() {return a.size();}void resize(int N) {a.resize(N);}int& operator[](int x) {return a[x];}void push_back(int V) {a.push_back(V);}friend Bigint operator*(Bigint x, int v) {for (int i = 0; i < x.size(); i++)x[i] = x[i] * v;for (int i = 0; i < x.size() - 1; i++)x[i + 1] += x[i] / 10, x[i] %= 10;while(x[x.size() - 1] >= 10)x.push_back(x[x.size() - 1] / 10), x[x.size() - 2] %= 10;return x;}void print() {for (int i = a.size() - 1; i >= 0; i--)cout << a[i];}
} ans1, ans2;
int main() {cin >> t >> n >> d;int s = 0;for (int i = 1; i <= t; i++)cin >> a[i], s += a[i];prepare();for (int i = 1; i <= n; i++) {int x, y; cin >> x >> y;add(a[y], 1), add(s, -1);s += d, a[y] += d;}for (int i = 1; i <= tot; i++) {if(num[i] < 0) {for (int j = 1; j <= -num[i]; j++)ans1 = ans1 * prime[i];}else {for (int j = 1; j <= num[i]; j++)ans2 = ans2 * prime[i];}}ans2.print(), putchar('/'), ans1.print();return 0;
}