题解 P5084 轮换式/P6296 轮换式 加强版
苹果蓝17
·
·
题解
题目传送门
更好的阅读体验
题意简述
题目分析
轮换式是典型的积和形式，直接考虑写成生成函数：
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) 即可。
$$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$，会方便一些。
#### 代码
```cpp
...
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;
}
```