P4935 口袋里的纸飞机 更优的解法
NaCly_Fish
·
·
题解
给出一个理论时间复杂度 \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）：
对于 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) 四种，由此也可以保证计算幂级数的乘方时，指数必定是整数，实现上会方便一些。