P6944 [ICPC2018 WF] Gem Island

Alex_Wei · 2022-11-18 19:24:30 · 题解

P6944 [ICPC2018 WF] Gem Island

我们抽象出一些信息描述最终方案，发现可设 c_i 表示第 i 个人手上有 c_i 颗宝石。

第 i 个人手上的第 j 颗宝石由前 j - 1 个宝石之一分裂得到，方案数 (c_i - 1)!。安排每天分裂哪个人手上的宝石，方案数 \dbinom {d} {c_1 - 1, c_2 - 1, \cdots, c_n - 1}。相乘得 d!，这说明所有可能的 c 出现的概率相同，因此答案可写为

其中 F(c) 表示 c_i 前 r 大的数的和。将 d! 除到分母上，我们需要计算 \sum F(c)。

因为要求数值前 r 大且 \sum c_i = n + d，所以考虑经典拆分数 DP。将所有 c_i 减去 1，答案加 r，限制变为 \sum c_i = d。

设 f_{S, i} / g_{S, i} 表示总和为 S，当前最大值有 i 个的方案数和总贡献。枚举 i'\leq i，则 f_{i, S} \dbinom {i} {i'} \to f_{i', S + i'}，(g_{i, S} + f_{i, S} \min(r, i'))\dbinom {i} {i'} \to g_{i', S + i'}。时间复杂度 \mathcal{O}(n ^ 3)。

#include <bits/stdc++.h>
using namespace std;
#define TIME 1e3 * clock() / CLOCKS_PER_SEC

constexpr int N = 500 + 5;
int n, d, r;
double f[N][N], g[N][N], C[N][N];

int main() {
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> d >> r;
  for(int i = 0; i <= n; i++)
    for(int j = 0; j <= i; j++)
      C[i][j] = j ? C[i - 1][j - 1] + C[i - 1][j] : 1;
  f[0][n] = 1, g[0][n] = r;
  for(int S = 0; S < d; S++)
    for(int i = 1; i <= n; i++)
      for(int _i = 1; _i <= i && S + _i <= d; _i++) {
        double c = C[i][_i];
        f[S + _i][_i] += f[S][i] * c;
        g[S + _i][_i] += (g[S][i] + f[S][i] * min(r, _i)) * c;
      }
  double F = 0, G = 0;
  for(int i = 1; i <= n; i++) F += f[d][i], G += g[d][i];
  printf("%.9lf\n", G / F);
  return cerr << "Time: " << TIME << " ms\n", 0;
}

加强版。

将数 v 的贡献拆成 \sum\limits_{j = 1} ^ {d} [v\geq j]，枚举 j，则每个方案对答案的贡献为 \min(i, r)，其中 i 是不小于 j 的数的个数。考虑算出恰有 i 个不小于 j 的数的方案数 f(i, j)。根据上述分析，\sum\limits_{j = 1} ^ d\sum\limits_{i = 0} ^ n f(i, j) \min(i, r) 即为所求。

钦定有 i 个数不小于 j，方案数为 g(i, j) = \dbinom {n} {i} \dbinom {d - ij + n - 1} {n - 1}。根据 g(i, j) = \sum\limits_{k = i} ^ n \dbinom {k} {i} f(k, j)，二项式反演得到 f(i, j) = \sum\limits_{k = i} ^ n (-1) ^ {k - i} \dbinom {k} {i} g(k, j)。

推式子：

对每个 k 预处理 h(k) = \sum\limits_{j = 1} ^ d g(k, j) 即可做到 \mathcal{O}(nm)。

#include <bits/stdc++.h>
using namespace std;
#define TIME 1e3 * clock() / CLOCKS_PER_SEC

constexpr int N = 1.5e7 + 5;
constexpr int mod = 998244353;
void add(int &x, int y) {x += y, x >= mod && (x -= mod);}
inline int ksm(int a, int b) {
  int s = 1;
  while(b) {
    if(b & 1) s = 1ll * s * a % mod;
    a = 1ll * a * a % mod, b >>= 1;
  }
  return s;
}
int fc[N], ifc[N];
int bin(int n, int m) {
  if(n < 0 || m > n) return 0;
  return 1ll * fc[n] * ifc[m] % mod * ifc[n - m] % mod;
}
int n, d, r, ans, g[N];

int main() {
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> d >> r;
  for(int i = fc[0] = 1; i < N; i++) fc[i] = 1ll * fc[i - 1] * i % mod;
  ifc[N - 1] = ksm(fc[N - 1], mod - 2);
  for(int i = N - 2; ~i; i--) ifc[i] = 1ll * ifc[i + 1] * (i + 1) % mod;
  for(int k = 1; k <= n; k++)
    for(int j = 1; j * k <= d; j++)
      add(g[k], 1ll * bin(n, k) * bin(d - k * j + n - 1, n - 1) % mod);
  for(int i = 1; i <= n; i++) {
    int s = 0;
    for(int k = i; k <= n; k++) {
      int coef = 1ll * bin(k, i) * g[k] % mod;
      if(k - i & 1) coef = mod - coef;
      add(s, coef);
    }
    add(ans, 1ll * min(i, r) * s % mod);
  }
  cout << (1ll * ans * ksm(bin(n + d - 1, d), mod - 2) + r) % mod << "\n";
  return cerr << "Time: " << TIME << " ms\n", 0;
}