清华集训合集

1/?

UOJ269 【清华集训2016】如何优雅地求和

请先思考后再展开

关于连续点值,你可能需要对下降幂多项式有所了解,总之我们可以nlogn求出$f(x)$的下降幂形式

$$
特殊情况:\sum_{k=0}^nC_n^kx^k(1-x)^{n-k}=\sum_{k=0}^n C_n^kx^k\sum_{j=0}^{n-k}C_{n-k}^j(-1)^jx^j=\sum_{i=0}^nC_n^ix^i(\sum_{j=0}^i C_i^j(-1)^j)=1 \\
a^{\underline b}(a<b)=0, Q(x^{\underline C})
=\sum_{k=C}^n k^{\underline C} C_n^k x^k (1-x)^{n-k}
=\sum_{k=C}^n k^{\underline C} \frac{n^{\underline C}*(n-C)!}{k^{\underline C}*(k-C)!(n-k)!} x^C x^{k-C} (1-x)^{n-k} \\
=n^{\underline C}x^C (\sum_{k=C}^n C_{n-C}^{k-C}x^{k-C}(1-x)^{n-k})
=n^{\underline C}x^C (\sum_{k=0}^{n-C} C_{n-C}^{k}x^{k}(1-x)^{n-k-C})
=n^{\underline C}x^C \\
f(x)=\sum_i a_ix^{\underline i},Q(f)=\sum_{i=0}^m a_in^{\underline i}x^i,O(nlogn)
$$

code

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/c7f8.html
转载请注明出处,谢谢!