ez problem 1
luogu_gza
·
·
学习·文化课
分享一个组合数学题，我应该已经给部分朋友推荐过了。
$$
\sum_{t=1}^{n}\sum_{r=0}^{n}(-1)^{t-1}\binom tr \binom nt \binom{p(n-t)}{m-rp} \equiv{\binom{np}{m}} \pmod{p^n}
$$
:::info[solution]
首先刻画一下 $\binom tr \binom nt \binom{p(n-t)}{m-np}$，这个其实是从 $np$ 个小球中选 $m$ 个小球，将 $np$ 个小球分为 $n$ 组，钦定 $r$ 组全选，$t-r$ 组全空。
那么你考虑一个方案对答案的贡献（其 $(-1)^{t-1}$ 之和）是什么呢？假设这个方案有 $a$ 组全选，$b$ 组全空，那么其贡献可以表述为：$\sum_{r=0}^{n}\sum_{t=1}^{n}(-1)^{t-1}C(a,r)C(b,t-r)=[a+b \neq 0]$。
那么 LHS 相较之 RHS 少计算了 $a+b=0$ 时候的方案，$a+b=0$ 时的方案个数为 $(2^p-2)^n$ 种，显然为 $p^n$ 的倍数，得证。
:::