题目

传送门 to CF

题目概要
有 $n$ 只小白鼠，有 $k$ 瓶药（其一是毒药）。共 $t$ 天时间，从第 $0$ 天开始，你可以给小白鼠任意喝药，次日你可以看到这些小白鼠的存活情况。

你需要在第 $t$ 天指出哪瓶药是毒药，且死亡的小白鼠不能超过 $p$ 。问最大的可行 $k$ 是多少。

对所有 $t\in [1,q]$ 都回答上面的问题。

思路

考虑一天中能获得的信息：将药按照 $2^n$ 种小鼠食用情况分类，则毒药会被确定在某一类中。

每一类的最大药瓶数是已知 $\mathtt{dp}$ 状态。因此记 $f_t(m)$ 为，现在还剩 $t$ 天，有 $m$ 只鼠的答案，则
$$f_t(m)=\sum _{i=n-p}^m\left(\genfrac{}{}{0ex}{}{m}{i}\right)f_{t-1}(i)$$

这样 $\mathcal{O}(pq)$ 也算是做完了。

但是 $\mathsf{Rainybunny}$ 融汇贯通，从信息熵的角度指出：枚举鼠的死亡情况和时间，可知最多能鉴别出的方案数为
$$f_t(m)=\sum _{i=0}^p\left(\genfrac{}{}{0ex}{}{m}{i}\right)t^i$$

这个式子随后被证明是正确的。我先从组合数学的角度出发，然而因为最初式子写错了，因此就是证不出；修好的推导如下。😓
∑ i = k m ( m i ) ∑ j = 0 i − k ( i j ) ( t − 1 ) j = ∑ i = k m ( m i ) ∑ j = 0 i − k ( i j ) ∑ p = 0 j ( j p ) t p ( − 1 ) j − p = ∑ p = 0 m − k ( m p ) t p ∑ j = p m − k ( m − p j − p ) ( − 1 ) j − p ∑ i = j + k m ( m − j i − j )

​i=k∑m​(im​)j=0∑i−k​(ji​)(t−1)j=i=k∑m​(im​)j=0∑i−k​(ji​)p=0∑j​(pj​)tp(−1)j−p=p=0∑m−k​(pm​)tpj=p∑m−k​(j−pm−p​)(−1)j−pi=j+k∑m​(i−jm−j​)​

只看 $t^p$ 以右。作换元 $n:=m-p$ 其值为
∑ j = 0 n − k ( n j ) ( − 1 ) j ∑ i = k n − j ( n − j i ) = ∑ i = k n ( n i ) ∑ j = 0 n − i ( n − i j ) ( − 1 ) j = ∑ i = k n ( n i ) [ i = n ] = 1

​j=0∑n−k​(jn​)(−1)ji=k∑n−j​(in−j​)=i=k∑n​(in​)j=0∑n−i​(jn−i​)(−1)j=i=k∑n​(in​)[i=n]=1​

证明是平凡的，但是发现结论并不是 “数学地”，因此颇让我惊奇。

重新考究这个 $f_t(m)={\sum }_{i=k}^m\left(\genfrac{}{}{0ex}{}{m}{i}\right)f_{t-1}(i)$，既然规定 $f_t(i)=0(i<k)$ 这个和式并没有范围限制，那么其 $\mathrm{EGF}$ 满足
$$F_t=\exp (x)\cdot F_{t-1}$$

底部值 $F_0={\sum }_{i⩾k}\frac{x^i}{i!}$ 故
[ x m ] F t = exp ⁡ ( t x ) F 0 = ∑ i = 0 m − k 1 ( m − i ) ! [ x i ] exp ⁡ ( t x ) = ∑ i = 0 m − k t i ( m − i ) ! ⋅ i !

[xm]Ft​​=exp(tx)F0​=i=0∑m−k​(m−i)!1​[xi]exp(tx)=i=0∑m−k​(m−i)!⋅i!ti​​

注意 $F_t$ 是 $\mathrm{EGF}$ 。结论即证。

得到该结论后，我们只需算 ${\sum }_{i=0}^p\left(\genfrac{}{}{0ex}{}{m}{i}\right)t^i$ 在 $t\in [1,q]$ 处的值。

多点求值似乎能够做到 $\mathcal{O}(q{\log }^{2}p)$ 么？错了，是 $\mathcal{O}(q\log p+p{\log }^{2}p)$ 。

因为该多项式次数只有 $p$，可以先求 $t\in [0,p]$ 然后不断点值平移。

然而模数是 $2^{32}$ 。即使我们认为可以 $\text{MTT}$，点值平移会涉及的除法也是个大问题。——估计要扩展到对 $2^{32+p+\log q}$ 取模，比较麻烦。

代码

搬题人改编了它，因此不能复制代码，故而不写了。