CF1770F 题解

\(\text{link}\) 。很困难的二进制计数。

前置知识 \(1\)：范德蒙德卷积推广。

即 \(\sum\limits_{a_1+a_2+\dots+a_n=k,a_i\in \N} \prod\limits_{j=1}^n\dbinom{b_i}{a_i}=\dbinom{b_1+b_2+\dots+b_n}{k}\)。这里给一个组合意义的证明。

\(RHS\) 相当于在 \(\sum b_i\) 个物品中选 \(k\) 个的方案数，\(LHS\) 相当于枚举对于每 \(b_i\) 各选了几个，且满足总和为 \(k\)。于是 \(LHS,RHS\) 所表示的组合意义的值是一样的。