Uoj#269 【清华集训2016】如何优雅地求和

发表于 分类于 ， ， 阅读次数：

题意：易知 是 次多项式，给出它的 个点值 。

给出 ，求

答案对 取模，，，时限 。

  • 前置芝士：下降幂多项式。

点值是连续的，我们容易把 表示成 个下降幂的线性组合。

现在我们对每个下降幂分别考虑贡献。下降幂和二项式系数比较有缘，所以会产生一些便利。 比较大，但是 较小， 仍然容易递推求出。

卷积实现点值和下降幂多项式系数之间的转换，复杂度 。

复杂度为 的算法也可能通过。