二项式定理

二项式定理

$\quad \quad \quad (x+y)^n =\sum_{k=0}^{n} {n \choose k} x^{n-k} y^k $

证明

\(\quad (x+y)^n=(x+y)*(x+y)*(x+y)*...\)
我们考虑多项式乘法\((a+b)*(a+b)=a*a+a*b+b*a+b*b\)
于是我们枚举每个因子相乘，可以发现\((x+y)^n\)每个括号里的 \(x\) 和 \(y\) 最多只能选一个，乘出来的每个单项式次数和必然为 \(n\) 。
知道这些，那我们再考虑\(x^{n-k}y^k\)会被选出来多少次，这其实也很好知道，无非就是 \(n\) 个 \(y\)
中选出了多少个呗，我们直接枚举即可，于是就得到了这个式子。

例题

推柿子题

设 \(cnt[i]\) 数组为字符中问号的前缀和。

那很简单列出原始式子

\begin{aligned}
ans&=\sum_{0 \leq L<R \leq n} (R-L)^{k} * \frac{1}{2^{cntR-cntL}}\\
&=\sum_{0 \leq L<R \leq n}\sum_{i=0}^{k}
{k \choose i} R^{k-i} (-L)^i *2^{-cntR} * 2^{cntL}\\
&=\sum_{i=0}^{k} {k \choose i} \sum_{R=1}^{n} R^{k-i} * 2^{-cntR} \sum_{L=0}^{R-1} (-L)^{i} * 2^{cntL}
\end{aligned}

我们就可以 \(O(nk)\) 预处理， \(O(n)\) 遍历，即可得到答案。