「UR #19」通用测评号 题解

---

题目链接

• https://uoj.ac/problem/514

和【集训队作业2018】喂鸽子 几乎一样的题 (

就是算是在总结 喂鸽子 的 $O(n ^ 2 k)$ 解法了.

解题思路

如果将操作视为序列, 大力生成函数, 容易得到 50 pts 的做法, 也就是官方题解中的算法 2. 和【UNR #3】百鸽笼 十分相似.

下文称 “放入至少 $b$ 单位的燃料” 为 “半满”, “填满 $a$ 单位的燃料” 为 “填满”.

首先对题意做一步转化, 只需计算出所有燃料舱全部半满之前, 每个燃料舱填满的概率再求和即可. 注意到燃料舱编号对答案没有影响, 不妨令填满的燃料舱编号为 $1$, 计算最终答案时乘 $n$ 就好了.

所求即满足第 $1$ 个燃料舱填满时, 不存在燃料舱仍未半满的概率. 考虑容斥, 枚举仍未半满的燃料舱个数 $m$, 同时记 $g_m$ 表示在共计 $m + 1$ 燃料舱中, 第 $1$ 个燃料舱填满时, 存在 $m$ 个燃料舱未半满的概率. (此处可直接将其余燃料舱忽略, 详见「PKUWC2018」猎人杀 中用到的 Trick) 可得

$$\sum_{m = 1} ^ {n - 1} (-1) ^ {m - 1} \binom{n - 1}{m}\ g_m$$

可以通过操作序列入手计算 $g_m$. 那么此处对操作序列的限制为 恰好 出现 $a$ 次编号 $1$, 同时有 $m$ 个编号出现次数 至多 为 $b - 1$.

但实际上, 序列中最后一次操作一定填入 $1$, 序列中未确定的位置只有 $i - 1$ 处. 因此其 EGF 为

$$F(x) = \frac{x ^ {a - 1} }{(a - 1)!} \cdot \left( \sum_{k = 0} ^ {b - 1} \frac{x ^ k}{k!} \right) ^ m = \frac{x ^ {a - 1} }{(a - 1)!}\ G ^ m (x)$$

枚举序列长度为 $i$, 那么 $g_m$ 可表示为

$$g_m = \sum_{i = 0} ^ {m (b - 1)} \frac{1}{(m + 1) ^ i} (i - 1)! \cdot [x ^ {i - 1}]\ \frac{x ^ {a - 1} }{(a - 1)!}\ G ^ m (x)$$

现在的问题在于如何快速计算 $G ^ m (x)$.

注意到 $G(x)$ 和 $e ^ x$ 的相似性, 并且我们知道 $(e ^ x)’ = e ^ x$. 那么可以尝试用类似的方法递推求出 $F(x)$. 具体地, 有

$$G'(x) = \left( \sum_{k = 0} ^ {b - 1} \frac{x ^ k}{k!} \right)' = \sum_{k = 1} ^ {b - 1} \frac{k \, x ^ {k - 1} }{k!} = G(x) - \frac{x ^ {b - 1} }{(b - 1)!}$$

那么对于 $G ^ m (x)$, 有

$$\big(G ^ m(x)\big)' = m \cdot G ^ {m - 1} (x) \cdot G'(x) = m \left( G ^ m(x) - \frac{x ^ {b - 1} }{(b - 1)!} G ^ {m - 1} (x) \right)$$

同时取项 $x ^ {i - 1}$ 系数, 可得

$$[x ^ {i - 1}] \big(G ^ m (x)\big)' = i \cdot [x ^ i] G ^ m(x) = m \left( [x ^ {i - 1}] G ^ m (x) - [x ^ {i - 1}] \frac{x ^ {b - 1} }{(b - 1)!} G ^ {m - 1} (x) \right)$$

此时 $[x ^ i] G ^ m (x)$ 可通过 $[x ^ {i - 1}]G ^ m(x)$, $[x ^ {i - 1}]G ^ {m - 1} (x)$ 得出, 递推计算即可. 时间复杂度 $O(n ^ 2 b)$.

这个技巧也在【集训队作业2018】喂鸽子 的某种 $O(n ^ 2 k)$ 做法中用到过.

代码实现

// UOJ #514
// DeP
#include <cstdio>
using namespace std;

const int MAXN = 255, MAXM = MAXN * MAXN, P = 998244353;

int fac[MAXM], ifac[MAXM], inv[MAXM];

inline int binom(int n, int m) {
  return (n < m)? 0: 1LL * fac[n] * ifac[m] % P * ifac[n - m] % P;
}

inline int fpow(int base, int b) {
  int ret = 1;
  while (b > 0) {
    if (b & 1) ret = 1LL * ret * base % P;
    base = 1LL * base * base % P, b >>= 1;
  }
  return ret;
}

void PolyPre(int N) {
  inv[1] = 1;
  for (int i = 2; i <= N; ++i)
    inv[i] = 1LL * inv[P % i] * (P - P / i) % P;
  ifac[0] = fac[0] = 1;
  for (int i = 1; i <= N; ++i) {
    fac[i] = 1LL * fac[i - 1] * i % P;
    ifac[i] = 1LL * ifac[i - 1] * inv[i] % P;
  }
}

int n, a, b;
int f[MAXN][MAXM], g[MAXN][MAXM];

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  scanf("%d%d%d", &n, &a, &b);

  PolyPre(n * a);
  f[0][0] = 1, g[0][b - 1] = ifac[b - 1];
  for (int m = 1; m <= n; ++m) {
    f[m][0] = 1, g[m][b - 1] = ifac[b - 1];
    for (int i = 1; i <= m * (b - 1); ++i) {
      f[m][i] = 1LL * m * inv[i] % P * (f[m][i - 1] - g[m - 1][i - 1] + P) % P;
      g[m][i + b - 1] = 1LL * f[m][i] * ifac[b - 1] % P;
    }
  }
  for (int m = 1; m <= n; ++m)
    for (int i = 0; i <= m * (b - 1); ++i)
      g[m][i + a - 1] = 1LL * ifac[a - 1] * f[m][i] % P;
  int ans = 0;
  for (int m = 1; m < n; ++m) {
    int s = 0, pw = fpow(inv[m + 1], a);
    for (int i = a; i <= m * (b - 1) + a; ++i) {
      s = (s + 1LL * fac[i - 1] * pw % P * g[m][i - 1] % P) % P;
      pw = 1LL * pw * inv[m + 1] % P;
    }
    s = 1LL * s * binom(n - 1, m) % P;
    ans = (ans + ((m & 1)? s: P - s)) % P;
  }
  ans = 1LL * ans * n % P;

  printf("%d\n", ans);
  return 0;
}

参考资料

• yhx-12243, [uoj514]通用测评号 题解
• UOJ Round #19 题解

---