IOI2021 集训队自选题 Gem Island 2

默认读者已经会了 ICPC2018 World Final Gem Island

下文的 $a_{i}$ 均表示分裂次数而非宝石个数

考虑期望的线性性，不难发现恰好有 $k$ 个人的分裂次数大于 $i$ 时，对答案有 $min (k, r)$ 的贡献，即答案为

$\sum_{i \geq 0} \sum_{k \geq 0} (\binom{n}{k}) ([x^{d}] {(\frac{1 - x^{i + 1}}{1 - x})}^{n - k} {(\frac{x^{i + 1}}{1 - x})}^{k}) min (k, r)$

首先可以把 $\frac{1}{1 - x}$ 都提出来并拆开 $min$ 分为两种情况

考虑求出了 $i = 0$ 时的多项式 $F (x)$ 答案即为 $[x^{d}] \frac{\sum_{i \geq 0} F (x^{i + 1})}{(1 - x)^{n}}$ 求出了 $F (x)$ 就可以用高维前缀和（狄利克雷前缀和）把每一次的系数贡献到它所有倍数的答案，就求出了分子，由于 $[x^{i}] (1 + x + x^{2} + \dots)^{n} = (\binom{n + i - 1}{n - 1})$ 不难直接求出答案，于是只考虑 $F (x)$

$\begin{aligned} F (x) = & r \sum_{k \geq r} (\binom{n}{k}) (1 - x)^{n - k} x^{k} + \sum_{k \leq r} k (\binom{n}{k}) (1 - x)^{n - k} x^{k} \\ = & r (\sum_{k \geq 0} (\binom{n}{k}) (1 - x)^{n - k} x^{k} - \sum_{k \leq r} (\binom{n}{k}) (1 - x)^{n - k} x^{k}) + n x \sum_{k \leq r} (\binom{n - 1}{k - 1}) (1 - x)^{(n - 1) - (k - 1)} x^{k - 1} \\ = & r - r \sum_{k \leq r} (\binom{n}{k}) (1 - x)^{n - k} x^{k} + n x \sum_{k \leq r - 1} (\binom{n - 1}{k}) (1 - x)^{n - 1 - k} x^{k} \end{aligned}$

不难发现化为了同一种问题，另外，其中常数项 $r$ 可以直接去掉，因为常数项都是不贡献到答案的，于是答案为

$\begin{matrix} (1) & - r \sum_{k \leq r} (\binom{n}{k}) (1 - x)^{n - k} x^{k} + n x \sum_{k \leq r - 1} (\binom{n - 1}{k}) (1 - x)^{n - 1 - k} x^{k} \end{matrix}$

考虑重新定义 $F (x) = \sum_{k \leq r} (\binom{n}{k}) (1 - x)^{n - k} x^{k}$ ，并定义 $f (x) = \sum_{k \leq r} (\binom{n}{k}) x^{k}$

发现

$\begin{aligned} f^{'} (x) = & \sum_{k \leq r} k (\binom{n}{k}) x^{k - 1} \\ = & n \sum_{k \leq r} (\binom{n - 1}{k - 1}) x^{k - 1} \end{aligned}$

这个形式看起来很能裂项相消，于是有：

$\begin{aligned} n f (x) - x f^{'} (x) = & n \sum_{k \leq r} (\binom{n}{k}) x^{k} - n \sum_{k \leq r} (\binom{n - 1}{k - 1}) x^{k} \\ = & n \sum_{k \leq r} (\binom{n - 1}{k}) x^{k} \\ = & f^{'} (x) + n (\binom{n - 1}{r}) x^{r} \end{aligned}$

得到：

$\begin{matrix} (2) & (1 + x) f^{'} (x) = n (f (x) - (\binom{n - 1}{r}) x^{r}) \end{matrix}$

将 $f (x)$ 带回 $F (x)$ ： $F (x) = (1 - x)^{n} f (\frac{x}{1 - x})$

对求导得：

考虑到带入式：

乘上得到：

再带回原式我们得到了

最后再积分即可，注意这么做之后常数项会丢失，观察式发现，对于前面一部分，常数项不会贡献到答案，但后一部分因为乘上了会贡献到答案到一次项，通过手算发现一次项系数为，直接手动加上即可

时间复杂度

题解

#生成函数 #组合计数 #高维前缀和

IOI2021 集训队自选题 Gem Island 2

https://blog.seniorious.cc/2020/gem-island-2/

作者

Seniorious

发布于

2020年12月25日

许可协议

JOI Final 2021 题解上一篇

「学习笔记」浅谈自相关多项式下一篇

0 条评论

未登录用户

支持 Markdown 语法

来做第一个留言的人吧！