CF622F The Sum of the k-th Powers

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

题意：给出 ，求

答案对 取模，，。

  • 结论： 是关于 的 次多项式。证明略。

记多项式 满足 ，在 取点值，可以用插值求出 的表达式。记 。

若计算出 再求 ，复杂度 ，无法通过。注意到只需要求 而不需要 的具体系数，将 直接代入插值公式得

其中常数 。

预处理阶乘，用线性筛求出 的 次幂，求和得各个 。复杂度 。