Sol
如何判断 $p^\alpha \mid \binom{n}{k}$ 是否成立：只需要知道 $\binom{n}{k}$ 中 $p$ 的次数是否大于等于 $\alpha$ 。
设 $f(n)$ 为 $n!$ 中 $p$ 的次数，显然有 $f(n) = \sum_{i=1}^\infty \lfloor \frac{n}{p^i} \rfloor$。而我们要做的就是检查 $f(n)-f(k)-f(n-k)$ 是否成立。
$f(n)$ 实际上相当于：$n$ 的 $p$ 进制表示去掉最后一位后的值 + $n$ 的 $p$ 进制表示去掉最后两位后的值 + $n$ 的 $p$ 进制表示去掉最后三位后的值 ……
考虑 $f(a+b)$ 和 $f(a)+f(b)$ 的区别：如果 $a+b$ 在 $p$ 进制下没有进位，那么两者显然相同；考虑如果 $a+b$ 在 $p^k$ 这一位进位了，那么相较于 $f(a)+f(b)$ ，$f(a+b)$ 在 $i\le k$ 的时候的贡献是不变的，但是在 $i=k+1$ 的时候就会多贡献 $1$ 。又因为这是两个数的加法，每一位至多进位一次，所以不会出现在第 $k$ 位的进位贡献到第 $k+2$ 位的情况。所以 $f(a+b)-(f(a)+f(b))$ 就是 $a+b$ 在 $p$ 进制加法中进位的次数。
令 $a=k,b=n-k$ ，我们相当于要统计满足 $0\le a,0\le b, a+b\le A$ 且 $a+b$ 进位次数不小于 $\alpha$ 的 $(a,b)$ 的数量。这是一个基础的数位 dp 问题。