我认为该题应该这样来推导。

double_zero · 2023-03-21 22:09:24 · 个人记录

当我们写出来一个暴力的时候，我们知道 dp(i,j) 表示选 i 个数，和为 j 的方案数，其系数是 (-1)^{i-k}\binom{i-1}{k-1}\dfrac{m}{j} 的，注意到，这东西仅跟 i,j 有关，但我们又不可能大力转移！所以很困难！

考虑记 dp(x,i,j) 为考虑了前 x 个数，选了 i 个数，和为 j 的方案数，考虑能否把它的容斥系数搞一起转移掉。再记 v(x,j)=\sum\limits _i (-1)^{i-k}\binom{i-1}{k-1}dp(x,i,j)。

考虑当前选 or 不选这个数。

若不选，则 \forall i,dp(x,i,j)\to dp(x+1,i,j)，即 v'(x+1,j)=\sum\limits_i(-1)^{i-k}\binom{i-1}{k-1}[dp'(x+1,i,j)+dp(x,i,j)]，即 \Delta=\sum\limits_i (-1)^{i-k}\binom{i-1}{k-1}dp(x,i,j)=v(x,j)，哦，所以直接能转移！

考虑选。

则 \forall i,dp(x,i,j)\to dp(x+1,i+1,j+p)，即 v(x+1,i+1,j+p)=\sum\limits_i (-1)^{i-k}\binom{i-1}{k-1}[dp(x+1,i,j+p)+dp(x,i-1,j)]，那么 \Delta=\sum\limits_i (-1)^{i-k}\binom{i-1}{k-1}dp(x,i-1,j)=\sum\limits_i (-1)^{i+1-k}\binom{i}{k-1}dp(x,i,j)，考虑拆开组合数，降下 i。

即

分别看。

不难发现，这一部分即 -v(x,j)。

好难做！因为组合数拆出来跟 i 会有关系。但因为 k 很小，倘若我们记 v_k(x,j)=\sum\limits_i (-1)^{i-k}\binom{i-1}{k-1}dp(x,i,j)，那么上面那个式子就是 v_{k-1}(x,j)！！

所以你就做完转移了。

考虑初始，dp(0,i,j) 只有 dp(0,0,0)=1，因此只考虑 i=0,j=0 的情况。

即 v_k(0,0)=(-1)^{-k}\binom{-1}{k-1}。

考虑 \binom{-1}{k-1}=(-1)^{k-1}，就你把下降幂带进去，就得到了。

因此 v_k(0,0)=-1，其他 =0。

总结，拒绝人类智慧，设个系数暴力转移。