PKUSC 2023 D1T3

Aleph1022 · 2023-05-17 18:19:27 · 个人记录

题目大意参考 ix35。

视 n+q 与 n 同阶。

菊花的情况如何做到 \Theta(n\log^2 n) 是熟知的：
问题可以泛化为给定分式列 u_1(x)/v_1(x), u_2(x)/v_2(x), \dots, u_{n+q}(x)/v_{n+q}(x)，其中 \deg u_k(x),\deg v_k(x) = \Theta(1) 及向量 a_0, a_1, a_2, \dots, a_n，要求向量 b_j = \sum_{i=0}^n a_i [x^i] \prod_{k=1}^j u_k(x)/v_k(x)。
进行转置，则问题变为 a_i = [x^i] \sum_{j=1}^{n+q} b_j \prod_{k=1}^j u_k(x)/v_k(x)，即求该分式列前缀积的带权求和。只需要分治 NTT 即可。

对于一般的情况，我们只需要使用动态 DP 的任意一种常用手法即可。这里以链分治为例：重链剖分后将整个问题进行离线，然后自下而上处理各重链，处理每条重链时在每个点处计算先前提到的子问题，而重链上的转移可以用 \Theta(1) 个信息的线性变换的复合表示。

总复杂度 \Theta(n \log^2 n + q \log^3 n)。