自动搬运

查看原文

来自洛谷，原作者为

	苹果蓝17 **

搬运于2025-08-24 22:19:27，当前版本为作者最后更新于2021-09-16 21:04:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题目传送门

更好的阅读体验

题意简述

• 现有 $n$ 个变量 $a_1,a_2,\cdots,a_n$，给出所有它们能组成的 $k$ 次轮换式的值 $f_k$，求 $\sum\limits_{i=1}^n a_i^m$。

• $n \leq 30000,m \leq 10^9$。

题目分析

轮换式是典型的积和形式，直接考虑写成生成函数：

$$f_k=[x^k]\prod\limits_{i=1}^n(1+a_ix)$$ $$F(x)=\prod\limits_{i=1}^n(1+a_ix)$$

发现这个累乘很难处理，考虑两边取 $\ln$：

$$\begin{aligned} \ln F(x) & =\sum\limits_{i=1}^n \ln(1+a_ix) \\ & =\sum\limits_{i=1}^n \sum\limits_{j \geq 1} -\dfrac{(-a_ix)^j}{j} \\ & =\sum\limits_{j \geq 1} \dfrac{(-1)^{j+1}}{j} x^j \sum\limits_{i=1}^n a_i^j \end{aligned} $$

于是答案为：

$$Ans=\dfrac{m}{(-1)^{m+1}}[x^m]\ln F(x)$$

只需要求出 $[x^m] \ln F(x)$ 即可。

---

$m$ 过大，肯定不能暴力求，考虑 $\ln$ 的递推求法：

$$G=\ln F$$ $$G'=\dfrac{F'}{F}$$ $$FG'=F'$$ $$kf_k=\sum\limits_{i=1}^{k} ig_{i}f_{k-i}$$

当 $k \leq n$ 时，暴力求 $\ln$ 即可，时间复杂度 $O(n \log n)$。

当 $k > n$ 时，有 $f_k=0$。

$$\begin{aligned} 0 & =\sum\limits_{i=1}^{k} ig_{i}f_{k-i} \\ & =\sum\limits_{i=0}^{k-1} (k-i)g_{k-i}f_i \\ & =\sum\limits_{i=0}^{n} (k-i)g_{k-i}f_i \\ & =kf_0 g_k+\sum\limits_{i=1}^{n} (k-i)g_{k-i}f_i \\ \end{aligned} $$$$kf_0 \cdot g_k=-\sum\limits_{i=1}^n (k-i)f_i \cdot g_{k-i} $$

这是非常显然的齐次线性递推的形式，总时间复杂度 $O(n \log n \log m)$。

代码里的 $g_k$ 代表实际是 $kg_k$，会方便一些。

代码

...
long long n,m;
long long A[N],F[N],G[N],P[N];

int main(){
	pre();
	cin>>n>>m;
	F[0]=1;
	for(int i=1;i<=n;i++) F[i]=rd();
	poly::Ln(G,F,n);
	for(int i=0;i<=n;i++) G[i]=G[i]*i%mod;
	for(int i=1;i<=n;i++) P[i]=(mod-F[i])%mod;
	cout<<Recursion::solve(P,G,m,n+1)*ID(m+1)%mod;
}