Uoj#654. 【ULR #2】后门

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

题意：对于长度为 的序列 ，定义 为将下标模 等于 的位置抽出组成的序列，保证 ，即 。

对于序列 定义权值函数 ： 现在给出长为 的序列 ，求 。

答案对 取模，时限 。

  • 原题：
  • 加强版：

你无需考虑输入序列 的耗时。

考虑贡献，设 为长为 的序列的第 个位置的贡献系数。我们的目标是求出 。然后答案可以这样计算： 考虑如何计算单个 。

将一种筛选记为 ，表示保留所有模 余 的位置。

筛选是可以叠加的。 两次筛选 叠加，则等效于筛选 。

相当于计数有多少种筛选序列叠加后最终得到单一的 。

注意到我们总是可以根据 唯一确定出 中的 ，所以我们可以只关心筛选中的模数 ，而不关心余数 。

考虑一个筛选序列符合要求的充要条件。记筛选序列为 。

  • 在筛选 生效后（只有最后一个 未生效），剩余的数至少有两个（否则就停止了）。

    记 （前 个筛选叠加），则充要条件为 （在前面有一个数）或 （在后面有一个数）。

    等价条件为 。

  • 在最后一步，筛选中的数变为单一的 。（并停止）

    最后一步的筛选 要满足 （将前面的条件取反）

    此外，还要满足 不超过 生效后的序列长度。

    这个长度为 （分别计算 前后的位置个数）。

    总的条件为

综上，我们只需要得知 与 即可判定一个筛选序列是否符合要求。

定义 为各元素 的有序整数序列乘积为 的方案数。

可由以下简单 DP 求解： 复杂度为 。

考虑枚举 ，则 的方案数可以确定。 得到 的方案数即为 。 上式容易整除分块计算。逐个计算 ，复杂度为 ，不够快。

考虑整除差分。

首先做一步转化，记 则 只需求 。

定义 注意到 当且仅当 ，且此时 。

于是有： 和 原本的递推式结合，即可得到 。

但有一个例外，当 时是 。

于是瓶颈就仅仅在于求出 。复杂度 。可以通过原题。

对于加强版，需要 求出 。

由递推式观察 的组合意义。

根据唯一分解，以各个指数为基，将数 看做高维空间的一个点 （坐标中大量 未写出）

这个点每一步可以走向维度坐标只减不增的区域，走到原点的方案数即为 。

不难发现，若两个坐标将维度任意排序后相同，则 函数的值也是相同的（不同维度的地位没有区别）。为了方便，我们约定坐标按照基底素数从小到大排序，并去掉 。

在这种定义下，在 中，仅仅只有 种不同的坐标。对每种坐标进行 DP 求出 函数值的复杂度可以忽略。

然后我们将所有坐标（以及对应函数值）插入字典树，便于检索。

接下来的任务就是对每个 求出其质因数分解坐标，并取出对应函数值。

筛出所有质数后，可以利用「树形筛」来得到每个数的坐标。

该筛法的思想是，从小到大考虑各个质因子，以及其指数（即逐位确定坐标）。配合字典树，可以快速找到对应的函数值。

可以发现，该筛法恰会访问 中的每个数各一次，且每个搜索树节点都不会在不合法的分支尝试中浪费超过 的时间。因此，该筛法的复杂度即为 。