题解 P7102 【[w3R1] 算】

· · 题解

题意：给出 m 项多项式 P(x) 以及常数 c。

定义 s(n)=\sum_{i=1}^nP(i)[i\perp n]。

给出 t，分别求 s(c),s(c^2),...,s(c^t) 的值。

答案对 998244353 取模，t,m\leq 2\times 10^5，c\leq 10^{18}，时限\texttt{1s}。

\begin{aligned} s(n) &=\sum_{i=1}^nP(i)[i\perp n]\\ &=\sum_{i=1}^nP(i)\sum_{d|n,d|i}\mu(d)\\ &=\sum_{d|n}\mu(d)\sum_{d|i}^nP(i)\\ &=\sum_{d|n}\mu(d)\sum_{d|i}^n\sum_{j=0}^{m-1}P[j]i^j\\ &=\sum_{d|n}\mu(d)\sum_{i=1}^{n/d}\sum_{j=0}^{m-1}P[j](id)^j\\ &=\sum_{j=0}^{m-1}P[j]\sum_{d|n}\mu(d)d^j\,\boxed{\sum_{i=1}^{n/d}i^j} \end{aligned}

后面的部分是自然数幂和。

自然数幂和的多项式为

\sum\limits_{i=0}^{n-1}i^k=S_k(n)=k!\sum\limits_{i=0}^k\dfrac{B[k-i]n^{i+1}}{(i+1)!}

其中 B 为伯努利数。它的的 EGF 为 \frac{x}{e^x-1}，其可以多项式求逆计算。

注意到只能对 [0,n-1] 求和，而且我们需要的是对 [1,n] 求和。 需要对 0,n 两项单独计算。

先考虑

\begin{aligned} s'(n)&=\sum\limits_{j=0}^{m-1}P[j]\sum\limits_{d|n}\mu(d)d^j\sum\limits_{i=0}^{n/d-1}i^j\\ &=\sum\limits_{j=0}^{m-1}P[j]\sum\limits_{d|n}\mu(d)d^jj!\sum\limits_{i=0}^j\dfrac{B[j-i](n/d)^{i+1}}{(i+1)!}\\ &=\sum\limits_{j=0}^{m-1}P[j]j!\sum\limits_{i=0}^j\dfrac{B[j-i]}{(i+1)!}\sum\limits_{d|n}\mu(d)d^j(n/d)^{i+1}\\ &=\sum\limits_{j=0}^{m-1}P[j]j!\sum\limits_{i=0}^j\dfrac{B[j-i]n^{i+1}}{(i+1)!}\sum\limits_{d|n}\mu(d)d^{j-i-1}\\ &=\sum\limits_{j=0}^{m-1}P[j]j!\sum\limits_{i=0}^j\dfrac{B[i]n^{j-i+1}}{(j-i+1)!}\sum\limits_{d|n}\mu(d)d^{i-1} \end{aligned}

考察积性函数 f_k=(\mu·id_k)*I，有

f_k(p^c)=\mu(1)id_k(1)+\mu(p)id_k(p)=1-p^k

不难发现 f_k(n) 的取值只与 n 的素因子集合有关。

由于 n^c 和 n 的素因子集合相同，可推知 f_k(n^c)=f_k(n)。

s'(n)=\sum\limits_{j=0}^{m-1}P[j]j!\sum\limits_{i=0}^j\dfrac{B[i]n^{j-i+1}}{(j-i+1)!}f_{i-1}(n)

用 c^k 替换 n ,同时注意到 f_{i-1}(c^k)=f_{i-1}(c)。

s'(c^k)=\sum\limits_{j=0}^{m-1}P[j]j!\sum\limits_{i=0}^j\dfrac{B[i](c^k)^{j-i+1}}{(j-i+1)!}f_{i-1}(c)

可以用 \rm Prho 分解求解积性函数 f_{0\sim(t-1)}(c)，这部分复杂度为 O\big(\sqrt[4]{c}+t\omega(c)\big)。

不妨设 F[i]=f_{i-1}(c)。

s'(c^k)=\sum\limits_{j=0}^{m-1}P[j]j!\sum\limits_{i=0}^j\dfrac{B[i]F[i](c^k)^{j-i+1}}{(j-i+1)!}

暂时用 x 替换 c^k。

R(x)=\sum\limits_{j=0}^{m-1}P[j]j!\sum\limits_{i=0}^j\dfrac{B[i]F[i]x^{j-i+1}}{(j-i+1)!}

不难发现 P[j]j!B[i]F[i] 会贡献到 x^{j-i+1} 的系数处，这是个差卷积。

计算出上述多项式之后，需要分别求 R(c),R(c^2),...,R(c^t) 的值。

使用 Chirp Z-Transform 即可。

\begin{aligned} s_1(n) &=\sum\limits_{j=0}^{m-1}P[j]\sum\limits_{d|n}\mu(d)d^j(n/d)^j\\ &=\sum\limits_{j=0}^{m-1}P[j]n^j\sum\limits_{d|n}\mu(d)\\ &=[n=1]\sum\limits_{j=0}^{m-1}P[j]\\ \end{aligned} \begin{aligned} s_0(n) &=\sum_{j=0}^{m-1}P[j]\sum_{d|n}\mu(d)d^j0^j\\ &=P[0]\sum_{d|n}\mu(d)\\ &=[n=1]P[0] \end{aligned}

最终

s(c^k)=s'(c^k)+s_1(c^k)-s_0(c^k)

复杂度为 O\big((m+t)\log(m+t)+\sqrt[4]{c}+m·\omega(c)\big)。