Luogu5072 [Ynoi2015] 盼君勿忘 发表于 2025-02-20 更新于 2025-02-26 分类于 算法竞赛 ， 题 ， 洛谷 阅读次数： 题意：给出序列 ，每次查询区间 的所有子序列分别去重后的和 。 这里的 每次询问单独给定，不保证是质数。 允许离线，，时限 。 分别考虑每个数的贡献。若在一个长度为 的区间中数 出现了 次，则贡献为 。 由于每次的 都不同，势必要单独计算每个 。 对于每个询问，首先用光速幂预处理，即可 求解 。 考虑根号分治。 记 为出现 次的数的总和，对于出现次数 的数，计算 。 对于出现次数 的数，只有 个，暴力维护其出现次数。 使用莫队即可维护上述信息，复杂度 。（ 同阶） 代码很好写。