问一道naive的数学和式题

学术版

66xyyd @ 2024-10-02 21:39:24

给出两个多项式函数 f(x)=\sum_{i=0}^{k_f}x^ia_i 和 g(x)=\sum_{i=0}^{k_g}x^ib_i，求：

\sum_{i=0}^{n}((-\frac{i}{p})^{p^{f(i)+g(i)}}f(p^i)g(p^{-i}) \bmod p)

保证 p 是 10^9 以内的质数，有没有 O(n\log n) 或 O(n\sqrt{n}) 的做法（最好只有一只log）

注：取模是对大和式每一项取模再相加

by 66xyyd @ 2024-10-02 21:40:46

@66xyyd 等一下手快打错了

by 66xyyd @ 2024-10-02 21:44:09

@66xyyd k_f 和 k_g 是和 n 同阶的，，

by _kpsum @ 2024-10-02 21:59:53

@66xyyd 不理解 g(p^{-i}) 在模 p 意义下是什么意思

by _kpsum @ 2024-10-02 22:00:42

@66xyyd 模 p 意义下 p 没有逆元阿

by 66xyyd @ 2024-10-03 17:19:02

@_kpsum 我打latex炸了

是 f((p-1)^i)g((p-1)^{-i})，当时把所有 p-1 打成了 p

by _kpsum @ 2024-10-03 17:19:20

@66xyyd 我看看

by _kpsum @ 2024-10-03 17:21:37

@66xyyd 多项式快速插值秒了 link

O(n \log^2 n)

by 66xyyd @ 2024-10-03 17:34:48

@_kpsum 可以O(n\log n) 吗？

by _kpsum @ 2024-10-03 17:45:35

@66xyyd 感觉不可以

|