P9138 [THUPC 2023 初赛] 公平合作
Alex_Wei
·
·
题解
P9138 [THUPC 2023 初赛] 公平合作
套路题，但是学到很多。
设先手和后手选择的容器的体积之和分别为 X 和 Y。很明显，后手可以根据先手的决策来决策，且策略唯一：不断选择容器直到 Y > X。
设 f_{i, j} 表示要求体积和大于 i 的前提下，体积和为 j 的概率，且 j 是第一次体积和大于 i。其等价于 X = i 时，Y = j 的概率。初始 f_{i, 0} = 1（i < 0）。从 f_{i - 1}\to f_i 时，将 f_{i - 1, i} 乘以 \frac 1 n 转移到所有 f_{i, i + a_j}。显然，对于任意 f_i，其有值的长度为 m = \max a_i。
设 p_i 表示当 X = i 时，i < Y \leq L 的概率，则 p_i = \sum_{j = i + 1} ^ L f_{i, j}。
设 q_i 表示当 X = i 时，先手获胜的概率，则先手可以继续选择容器或停止，因此 q_i = \max(1 - p_i, \frac {1} {n}\sum_{j} q_{i + a_j})。p_i 和 1 - q_i 的区别在于对于 p_i，先手可以继续决策，但 q_i 只允许后手决策。
设 C = L - m，因为 X 最终必然落在 (C, L] 之间，所以答案等于 \sum_{i = C + 1} ^ L f_{C, i} q_i。
现在只要求 f_C。
注意这样得到的值是反过来的，也就是下标较小的值为多项式较高次项的系数，所以先翻转系数（$x ^ i$ 前的系数翻转到 $x ^ {m - i - 1}$ 前），发现 $[x ^ k]$ 等于某个 $f_{i, i + k + 1}$。又因为 $x ^ m$ 模 $A$ 得到的多项式系数翻转后，$[x ^ k]$ 等于 $f_{0, k + 1}$，可知 $x ^ L \bmod A$ 处理后得到 $f_{L - m}$，即我们要求的 $f_C$。倍增 + 暴力多项式乘法 + 暴力多项式取模即可。
时间复杂度 $\mathcal{O}(m ^ 2\log L)$。
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
bool Mbe;
constexpr int N = 4e3 + 5;
int n, mx, L;
double w, a[N], f[N], g[N], p[N], q[N];
void mul(double *f, double *g) { // 计算 f * g mod A
static double h[N];
memset(h, 0, sizeof(h));
for(int i = 0; i < mx; i++)
for(int j = 0; j < mx; j++)
h[i + j] += f[i] * g[j];
for(int i = mx * 2 - 2; i >= mx; i--)
for(int j = 1; j <= mx; j++)
h[i - j] += h[i] * a[j];
for(int i = 0; i < mx; i++) f[i] = h[i];
}
bool Med;
int main() {
fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifdef ALEX_WEI
FILE* IN = freopen("1.in", "r", stdin);
FILE* OUT = freopen("1.out", "w", stdout);
#endif
cin >> n >> L, w = 1.0 / n;
for(int i = 1, v; i <= n; i++) {
cin >> v, mx = max(mx, v), a[v] += w;
// a 表示多项式对 A 取模时的系数，而不是 A
}
f[0] = 1, g[1] = 1;
while(L) { // 计算 x ^ L mod A
if(L & 1) mul(f, g);
mul(g, g), L >>= 1;
}
reverse(f, f + mx);
// 设 C = L - mx, f[i] 表示要求 > C 时，取到 C + i + 1 的概率
memcpy(g, f, sizeof(f));
// 接下来从 0 到 mx - 1 枚举 i，其中 g[i + j] 表示：
// 在循环开头，要求 Y > C + i 时 Y = C + i + j + 1 的概率
// 在循环结尾，要求 Y > C + i + 1 时 Y = C + i + j + 1 的概率
p[0] = 1;
// 计算 p[i] 表示 X = C + i + 1 时，后手的 Y 在 (C + i + 1, L] 之间的概率
for(int i = 0; i < mx; i++) {
if(i) p[i] = p[i - 1];
for(int j = 1; j <= mx; j++) { // 后手在 Y = C + i + 1 时必须继续选择容器
if(i + j >= mx) p[i] -= g[i] * a[j];
// 当 i + j >= mx 时，Y = C + i + j + 1 > L，超出限制，g[i] * a[j] 不会贡献至 p[i]
else g[i + j] += g[i] * a[j];
// 否则累加入 Y = C + i + j + 1 对应的 g[i + j]
}
}
double ans = 0;
for(int i = mx - 1; ~i; i--) {
// 计算 q[i] 表示 X = C + i + 1 时的胜率，p 和 q 的区别在于对于后者，先手还可以继续选择
// 要么不选容器，胜率为 p[i]；要么选容器，从接下来的 q 转移
for(int j = 1; i + j < mx; j++) q[i] += q[i + j] * a[j];
q[i] = max(q[i], 1 - p[i]);
ans += f[i] * q[i];
}
printf("%.12lf\n", ans);
cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
return 0;
}
```