自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:05:26，当前版本为作者最后更新于2024-06-27 19:06:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

给出一个理论时间复杂度 $\Theta(P \log P+n\log n)$ 的算法，但是常数可能比较大。

---

前面的做法和官方题解是一致的，我们可以枚举 $r$，计算有多少个序列会生成 $r$。

设 $s_i$ 表示 $[1,R]$ 范围内的整数中，有多少个和 $i$ 在模 $P$ 下同余。由于 $s_i$ 只有两种取值，我们设较小的为 $L$（较大的就是 $L+1$）。然后统计出三个数组（其中 $1\leq i < j <P$）：

• $A_r$：表示 $ij \equiv r \pmod P$，且 $s_i=s_j=L$ 的有序数对数量。

• $B_r$：表示 $ij \equiv r \pmod P$，且 $|s_i-s_j|=1$ 的有序数对数量。

• $C_r$：表示 $ij \equiv r \pmod P$，且 $s_i = s_j=L+1$ 的有序数对数量。

对于 $r\neq 0$，能够生成 $r$ 的序列数量就是

$$R^n-n^{A_r}(\text e^{Lx}+\text e^{(L+1)x}-1)^{B_r}(2\text e^{(L+1)x}-1)^{C_r}\text e^{Lx} $$

而 $r=0$ 很简单，数量就是 $R^n-(R-L)^n$。

每次暴力地 $\Theta(n^2)$ 计算，然后开个 map 存一下答案就可以通过这题了。

---

官方题解用到了一个猜想：本质不同的 $(A_r,B_r,C_r)$ 的数量是 $\mathcal O(\sqrt P)$ 级别的。我也没能将其证明或证伪，不过通过另一种思路，可以做到更优的时间复杂度。

我们设 $A_r'$ 和 $C_r'$ 分别是 $i$ 和 $j$ 不限制大小关系的情况下，按原规则统计的数量，我们将说明：

由 $A_r'$ 就可以唯一确定出 $B_r$ 和 $C_r'$。

首先有一个显然的关系：$A_r'+2B_r+C_r'=P-1$；
然后还有一个是：$A_r'+B_r=|S|$，其中 $S=\{i \mid s_i=L \ , \ 1\leq i <P \}$。

其中第二个式子中左侧的意义是：选的 $i$ 需要 $s_i=L$，而 $j$ 没有限制。显然对于每个 $i$，都存在一个 $j$ 使得 $ij\equiv r \pmod P$，所以总数就是等式右侧了。

然后如何得到真正的 $A_r$ 呢？$A_r'$ 减去 $i^2\equiv r \pmod P$ 且 $s_i=L$ 的解的个数就是 $2A_r$，由此也直接得到 $A_r'-2A_r\leq 2$。对于 $C_r$ 的计算也是一样的。

至此，聪明的你能想到接下来该怎么做吗？

---

我们设：

$$F(i,j,k)=n^{(k-i)/2}(\text e^{Lx}+\text e^{(L+1)x}-1)^{|S|-k}(2\text e^{(L+1)x}-1)^{(P-1-2|S|+k-j)/2}\text e^{Lx} $$

其中 $i,j \in \{ 0,1,2\}$。对于每组 $i,j$ 我们都能以 $\Theta(P \log P+n \log n)$ 的时间复杂度计算出所有 $F(i,j,k) \ (0\leq k< P)$，因为这是经典问题。

这样对于每个 $r$，能生成 $r$ 的序列数量就是 $R^n-F(A_r'-2A_r,C_r'-2C_r,A_r')$。

最后我们还要快速算出所有 $A_r'$，这个做法也在 [SDOI2015] 序列统计 中出现过了。我们只需要把所有 $s_i=L$ 的 $i$ 取离散对数，然后计算一次卷积即可。

---

update：我们实际上并不需要对每组 $(i,j)$ 都计算，因为可能出现的 $(i,j)$ 只有 $(0,0),(0,2),(1,1),(2,0)$ 四种，由此也可以保证计算幂级数的乘方时，指数必定是整数，实现上会方便一些。