自动搬运

查看原文

来自洛谷，原作者为

	command_block 众水皆昂首，饮月唯我一。

搬运于2025-08-24 22:26:39，当前版本为作者最后更新于2020-11-28 18:38:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意：给出 $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}$。

---

• 前置知识：Chirp Z-Transform

  给出多项式 $F(x)$ 和常数 $c$，可以卷积求出 $F(1),F(c),F(c^2),\dots,F(c^{m-1})$。

---

$$\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 即可。

---

• 单独计算 $n^k$ 项

$$\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} $$

---

• 单独计算 $0^k$ 项

$$\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)$。