自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:45:43，当前版本为作者最后更新于2023-03-15 14:28:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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$。

$f$ 的形式让我们想到常系数齐次线性递推，但它不是严格意义上的线性递推，因为线性递推是每次求出一个元素，而 $f$ 是每次用一个元素贡献它后面的元素。但是我们可以借用线性递推的思想：多项式取模。对于每个 $a_i$，为了让 $\frac 1 n [x ^ k]$ 贡献至 $[x ^ {k - a_j}]$，我们构造 $A = x ^ m - \sum_{j = 1} ^ n \frac 1 n x ^ {m - a_j}$。考虑 $c_k x ^ k$ 模 $A$，发现 $\frac {c_k} {n}$ 会贡献到每个 $x ^ {k - a_j}$ 前的系数，符合我们的要求。

注意这样得到的值是反过来的，也就是下标较小的值为多项式较高次项的系数，所以先翻转系数（$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)$。

#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;
}