Luogu7102 [w3R1] 算 发表于 2025-02-27 更新于 2025-02-26 分类于 算法竞赛 ， 题 ， 洛谷 阅读次数： 题意：给出 项多项式 以及常数 。 定义 。 给出 ，分别求 的值。 答案对 取模，，，时限 。 前置知识：Chirp Z-Transform 给出多项式 和常数 ，可以卷积求出 。 后面的部分是自然数幂和。 自然数幂和的多项式为 其中 为伯努利数。它的的 EGF 为 ，其可以多项式求逆计算。 注意到只能对 求和，而且我们需要的是对 求和。 需要对 两项单独计算。 微调后的求和 先考虑 考察积性函数 ，有 不难发现 的取值只与 的素因子集合有关。 由于 和 的素因子集合相同，可推知 。 用 替换 ,同时注意到 。 可以用 分解求解积性函数 ，这部分复杂度为 。 不妨设 。 暂时用 替换 。 不难发现 会贡献到 的系数处，这是个差卷积。 计算出上述多项式之后，需要分别求 的值。 使用 Chirp Z-Transform 即可。 单独计算 项 单独计算 项 最终 复杂度为 。