「营业日志 2021.1.26」多询问组合数前缀和
Elegia
·
·
个人记录
And if we don't survive
I'd rather die than live a lie
——《Nexus》
令
F(n,m) = \sum_{k=0}^{m} \binom n k
询问 N 次 F(n,m)，满足 n,m\le N。
本问题的寻常做法是基于 n,m 任何一维进行 \pm 1 的操作只需要 O(1) 计算修改。那么根据莫队可以规划一条 O(N^{3/2}) 级别的路径。
能不能稍微给力一点啊？
我们考虑通过整式递推方法加速。
设向量 \mathbf V_{n,m} = \begin{bmatrix} F(n,m) & \binom n m \end{bmatrix} = \begin{bmatrix}x & y\end{bmatrix}，那么有横向转移
\mathbf V_{n,m+1} = \begin{bmatrix}
x+\frac{n-m}{m+1}y & \frac{n-m}{m+1}y
\end{bmatrix} = \mathbf V_{n,m} \begin{bmatrix}
1 & 0\\
\frac{n-m}{m+1} & \frac{n-m}{m+1}
\end{bmatrix}
以及纵向转移
\mathbf V_{n+1,m} = \begin{bmatrix}
2x-y & \frac{n+1}{n-m+1} y
\end{bmatrix} = \mathbf V_{n,m} \begin{bmatrix}
2 & 0\\
-1 & \frac{n+1}{n-m+1}
\end{bmatrix}
设块大小 B\le N^{1/2}，那么我们可以先撒出所有 (iB,jB) 位置的 \mathbf V 值，此时对于每个 i，我们可以通过 FFT-倍增-拉格朗日插值在 \Theta((N/B)\log N) 的时间完成。因此这部分的总共代价是 \Theta((N/B)^2\log N)。
对于单组询问，可以 \Theta(B^{1/2}\log N) 从 (i,j) = (\lfloor n/B\rfloor,\lfloor m/B\rfloor) 转移到其，因此总共复杂度为 \Theta((N/B)^2\log N + NB^{1/2}\log N)，当 B=\Theta(N^{2/5}) 时得到复杂度 \Theta(N^{6/5}\log N)。
能不能稍微再给力一点啊？
都做到这个份上了，你难道不觉得这个问题可以 polylog 吗？
设当前的 B=N2^{-k}，对于每个 (2iB,2jB) 有可能有一维增加 B，总共有 N/2B 个位置要处理，可以 \Theta(B\log B) 算出乘积，然后 \Theta(\sum N_i\log^2 N_i) 多点求值，一层的复杂度是 \Theta(N\log^2N)，总共有 \log_2N 层，总共复杂度为 \Theta(N\log^3N)。
至于能不能把 \log 的指数降下来一点，这件事先鸽着。
UPD: \Theta(N\log^2N)，djq_cpp，于 2021 年夏天。
tutorial