CF643F Bears and Juice

· · 题解

给出一个不一样的推导方式。

首先令 p=\min(p,n-1)，因为多出来的床肯定用不上。记 f_{t,i,j} 为有 t 天，i 头熊，床数为 j 时最多的酒桶数。

首先考虑 f_{1,n,p} 怎么求，我们发现熊有 \sum\limits_{i=0}^p\binom{n}{i} 种不同的睡觉方式，把每种方式对应一个酒桶，所以 f_{1,n,p}=\sum\limits_{i=0}^p\binom{n}{i}。

对于 i>1 的情况，如果仍用原来的方案，同一种方式对应一个酒桶，则显然很亏。考虑算出一种方式最多可对应多少个酒桶，假设第一天时睡觉的熊的集合为 S，则答案一定在 S 对应的酒桶中，此时还剩下 n-|S| 头熊，p-|S| 张床。那么最多的数量就是 f_{t-1,n-|S|,p-|S|}，于是我们可以得出一个 dp 的形式。

我们发现转移只和 |S| 有关，并且 f 的第二维可以去掉。于是得出转移：

f_{i,j}=\sum\limits_{k=j}^p\binom{n-p+k}{k-j}f_{i-1,k}

直接 dp 复杂度是 O(p^2q) 的，考虑优化。

通过转移式子发现组合数可以抵消一些，所以 f_{n,m} 为：

\sum\limits_{\{a_n\},\sum a=p-m}\frac{n!}{(n-\sum a)!\prod\limits_{i=1}^na_i!} =\sum\limits_{\{a_n\},\sum a=p-m}\frac{n!(\sum a)!}{(n-\sum a)!(\sum a)!\prod\limits_{i=1}^na_i!} =\binom{n}{p-m}\sum\limits_{\{a_n\},\sum a=p-m}\frac{(\sum a)!}{\prod\limits_{i=1}^na_i!}

我们惊奇地发现后面一坨其实是多项式的展开的系数，得出 f_{n,m}=\binom{n}{p-m}n^{p-m}。

然后就可以 O(pq) 直接算了。

但是，这道题还有个小坑，模数是 2^{32} 。

我们可以直接exLucas 或暴力分解质因数把组合数中的质因数 2 提出来，剩下的部分与模数互质可以直接除，最后再把 2 乘进去即可。

code