形如 F(cx) = P(x)F(x) + Q(x) 的 nlogn 解法
飞雨烟雁
·
·
算法·理论
近期遇到了两次形如 F(cx)=P(x)F(x)+Q(x) 的方程。一次是 一道积分题及引发的思考 中最后的方程，另一次是 ABC333F O(n log n) Solution 中算法一的方程。于是自己想了一下，发现这一类方程应该是可以在 O(n\log n) 时间内解决的。
问题描述： 已知多项式 F(x) 满足 F(cx)=P(x)F(x)+Q(x)，其中 P,Q 已知，试求出 F(x) 的前 n 项。（F(x) 可能多解，仅求特解）
Case 1：P(x)=1
也就是 F(cx)=F(x)+Q(x)，此时直接提取系数即可。
\begin{aligned}[x^k]F(cx)&=[x^k]F(x)+[x^k]Q(x)\\c^kf_k&=f_k+q_k\\f_k&=\frac{q_k}{c^k-1}\end{aligned}
至于 f_0，它可以是任意常数。
Case 2：Q(x)=0
即 F(cx)=P(x)F(x)。这里需做讨论。
F(x)=\exp \bigg(\sum_{k\ge 1} \dfrac{[x^k]\ln P(x)}{c^k-1}x^k\bigg)
Case 3：其他情况
仍是作换元，令 F(x)=G(x)R(x)，则：
G(cx)R(cx)=G(x)P(x)R(x)+Q(x)
令 R(cx)=P(x)R(x)，这里的 R(x) 可以由 Case 2 在 O(n\log n) 时间内给出。那么有：
G(cx)=G(x)+\dfrac{Q(x)}{R(cx)}
这是 Case 1，G(x) 自然可在 O(n\log n) 内求出，最后做卷积 F(x)=G(x)* R(x) 即可。
接着看之前遇到的两个问题，第一个是：
F(3x)=F(x)\Big(\frac {e^x+1}{2}\Big)
这是 Case 2 里的第一种情况，直接代公式即可：
F(x)=\exp \bigg(\sum_{k\ge 1} \dfrac{[x^k]\ln (\frac{e^x+1}{2})}{3^k-1}x^k\bigg)
第二个是：
F(2x)=e^xF(x)+x
这是 Case 3，R(x) 满足 R(2x)=e^xR(x)，取 R(x)=e^x。则 G(x) 满足：
G(2x)=G(x)+xe^{-2x}
这个可以 \Theta(n) 求解，于是 F(x) 可在 O(n\log n) 时间内求出。
F(x)=e^x\bigg(\sum_{k\ge 1}\dfrac{(-2)^{k-1}x^k}{(k-1)!(2^k-1)}\bigg)
Update 2024.1.21：
我在实操一个概率问题时，发现这个解法是有缺陷的。
在 Case 2 中，如果 P(0)=0，那 F(x) 只有平凡解 0。但是在 Case 3 中，P(0)=0 时也可以有非平凡解，这时的 R(x) 就不能用 Case 2 的方法去解了。
举个例子：F(2x)=(e^x-1)F(x)+e^x，这个方程的解显然可以为 F(x)=e^x。但是它却没法用上面的方法求解。我尝试了一些方法去修改上面的做法，目前还没有什么突破。