求助证明，悬赏10r，救救孩子
查看原帖
求助证明，悬赏10r，救救孩子
900567
Poemsunny楼主2025/1/10 09:35

这道题我的解法是和这篇题解一样的 dp，最后统计答案的时候我是枚举的最大边计算贡献，最后得到的式子是这样的

ans=1m+1∑k=1m1(mk)⋅∑x∈S(m−dS−dU−S)∑i=0k−1gS,igU−S,k−1−ians=\frac{1}{m+1}\sum_{k=1}^{m}\frac{1}{\binom{m}{k}}·\sum_{x\in S}(m-d_S-d_{U-S})\sum_{i=0}^{k-1}g_{S,i}g_{U-S,k-1-i}

然而题解中最终答案是这样的

ans=1m+1∑k=0mfU,k(dUk)ans=\frac{1}{m+1}\sum_{k=0}^m\frac{f_{U,k}}{\binom{d_U}{k}}

这两个都是对的，但是我想知道可不可以通过数学方法从一个推导到另一个，从而证明它们两个相等？

求助各位大佬，我将给首个证出来的大佬 10r 以表感谢/kel/kel/kel

2025/1/10 09:35