P5591 小猪佩奇学数学题解

怎么拖到现在才开始写题解啊。

我不会啊。这咋做啊。

首先就是整除并不好做。我们因此考虑使用 转化一下：

考虑左侧的

这个东西很像二项式定理，因此我们朝着这个方向去凑。考虑把 写成 的形式。

组合意义合并一下两个组合数：

提出一个 。

做变量代换 ，此时要把 替换成 。

显然 是 。将求和下标从 开始，然后就是标准的二项式定理！

太棒了。但是考虑右侧的

怎么处理。

并不好处理啊！

我们如果把 替换成任意一个数 这个都很好算，就是一个二项式定理。

我们不妨假设我们能算出这个式子

其中的一种可能就是把 替换成 。

我们希望通过若干项 来凑出我们想到的答案。

也就是说，我们希望构造一组 使得

继续观察一下。

请注意最后这个式子等于

让这个两个式子相等，有一个简单的想法就是令 。

对于相同的 ，我们把 看成一组向量，我们就是要用若干个向量凑出来指定的向量。

此处我们要凑出来的向量就是第 维为 的向量。

由于两个向量都是 维的，根据线性代数的理论，我们最多只需要使用 个线性无关的向量就可以凑出来了。

一个简单的想法就是随便取 个 ，让 ，之后高斯消元解一个线性方程组即可。

但是，这并没有用啊！复杂度并没有更优啊。

我们不妨继续观察。 有一个很关键的性质，就是周期性。也就是说，。

因此，我们可以想到用另外一个周期为 的东西来凑出我们的目标向量，然后我们就可以把向量的长度截断到 ，而 只有 ！

那么，有什么东西的 呢？两边除以 发现

也就是说， 是 次单位根之一！

而 次单位根恰好有 个！

因此我们就选用这 个单位根来作为 。

此时问题变成了，我们有 个向量，其中第 个向量的第 维是 。

但是，如果我们每次都要解出来一个线性方程组， 的时间复杂度仍然无法接受。我们考虑用人类智慧提前解出来。

一个简单的想法是用我们这组基凑出标准正交基的每个向量，也就是仅有一个维度是 ，其余维度都是 的向量。

不妨从最简单的开始。

不妨另本原单位根为 。那么上面的式子也可以写成

观察发现 就是一个解（其实挺难发现的！但是除了自己解一下没什么好办法）。

这其实就是单位根反演的内容。

证明就是带入等比数列求和公式算一下，第 个维度公比为 ，当 不是 的时候，和就是 。由于 是本原 次单位根，因此 ，因而该式子分子为 。对于 的情况，就是 个 加起来，最终就是 。

另外，我们发现，对于我们选取的第 个向量，只需要乘上 就能让这个向量每个维度向后循环位移一位。

因此我们就可以构造出

的解。就是。

这样，我们就只需要凑出来向量的每个维度，把系数加起来即可。

但是，暴力计算系数的复杂度是 ，仍然无法接受。不过我们已经十分接近正解了！

继续观察，由于这个向量第 维就是 ，因此第 个向量的系数就是

我们希望快速计算这个。

我们把 写成 的形式（变量名要不够用了 QWQ）。

交换求和号。

请注意，现在右侧成了等比数列求和。这里不妨先假设 。

和 无关的提到外面来。

我们再次运用等比数列求和公式。

此时已经可以算了。直接快速幂计算即可。注意前面有一个 。因此最后的系数就是 。需要特判 的情况，此时系数为 。

对于对 取模的情况，将利用原根构造模意义下的本原单位根即可，相关结论可以看 OI-wiki，这里不过多展开。

参考代码。