自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:26:50，当前版本为作者最后更新于2024-06-05 03:58:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

首先要知道一点：$\upsilon(\pi)$ 就是 $n$ 减去排列 $\pi$ 中环的数量。
那么设有 $i$ 个环，其中 $j$ 个是自环（不动点）的排列数为 $f_{i,j}$，直接按题意可以写出答案是

$$S_n=2\sum_{i=0}^n[(n-i)\bmod 2=1]\sum_{j=0}^if_{i,j} \frac{n-i}{j+1} $$

对于 $f_{i,j}$，可以直接从 $n$ 个点中选出 $j$ 个作为不动点，剩下的 $n-j$ 个点都属于大小至少为 $2$ 的 $i-j$ 个环，即：

$$f_{i,j}=\binom nj (n-j)![x^{n-j}] \frac{(-\ln(1-x)-x)^{i-j}}{(i-j)!} $$

带回到原式中，推导一下：

$$\begin{aligned}S_n &=2\sum_{j=0}^n \binom nj \frac{(n-j)!}{j+1}[x^{n-j}]\sum_{i=j}^n[(n-i)\bmod 2=1] \frac{(-\ln(1-x)-x)^{i-j}}{(i-j)!}(n-i) \\ &= 2[x^n]\sum_{j=0}^n \binom nj \frac{(n-j)!}{j+1} x^j\sum_{i=0}^{n-j}[(n-j-i)\bmod 2=1] \frac{(-\ln(1-x)-x)^i}{i!} (n-j-i)\end{aligned} $$

这里先暂停，内层和式中 $i$ 的上界是 $n-j$。但 $i>n-j$ 时单项 $x$ 的最低次已经大于 $n-j$，对答案不会有贡献，我们可以将上界取到无穷大，这样内层就是：

$$\frac 12\sum_{i=0}^\infty(1-(-1)^{n-j-i}) \frac{(-\ln(1-x)-x)^i}{i!}(n-j-i) $$$$=\frac 12 \left( \frac{\text e^{-x}}{1-x}(n-j+\ln(1+x)+x)-(-1)^{n-j}\text e^x(1-x)(n-j-\ln(1-x)-x)\right) $$

带回去就是：

$$S_n=n![x^n]\sum_{j=0}^n \frac{x^j}{(j+1)!} \left( \frac{\text e^{-x}}{1-x}(n-j+\ln(1-x)+x)-(-1)^{n-j}\text e^x(1-x)(n-j-\ln(1-x)-x)\right) $$

虽然这样就可以 $\Theta(n)$ 计算了（整式递推出 $\text e^{-x}\ln(1-x)$ 与 $\text e^x \ln(1-x)$ 的系数即可），不过（为了装 B）我们可以考虑求出 $S_n$ 的 EGF。

那么还是可以把 $j$ 的上界取到无穷，再将上式整理一下，会得到许多形如 $n f(x)$ 或 $(-1)^n nf(x)$ 的部分，这样的单项会容易计算：

$$\sum_{n=0}^\infty z^n n[x^n]f(x)=\sum_{n=0}^\infty z^n [x^n](xf'(x))=zf'(z) $$

因此：

$$\begin{aligned}\sum_{n=0}^\infty \frac{z^n}{n!}S_n &=\sum_{j=0}^\infty \frac{z^j}{(j+1)!}\left( \frac{\text e^{-z}}{1-z}(-j+\ln(1-z)+z)\right) \\ &-\sum_{j=0}^\infty \frac{z^j}{(j+1)!}\left( \text e^{-z}(1+z)(-j-\ln(1+z)+z)\right) \\ &+ z\left( \sum_{j=0}^\infty \frac{z^j}{(j+1)!} \frac{\text e^{-z}}{1-z}\right)' \\ &- z \left(\sum_{j=0}^\infty \frac{z^j}{(j+1)!}\text e^{-z}(1+z)\right)'\end{aligned} $$

这个四个部分就都好办了，只有这里相对麻烦：

$$\sum_{j=0}^\infty \frac{z^j}{(j+1)!}j=\left( \sum_{j=0}^\infty \frac{z^j}{(j+1)!}\right)'z=\left(\frac{\text e^z-1}{z} \right)'z $$

最终我们可以得到（这与官方题解所给出的 EGF 是一致的）：

$$\sum_{n=0}^\infty \frac{z^n}{n!}S_n=\frac{1-\text e^{-z}}{z(1-z)^2}((2-z)z^2+(1-z)\ln(1-z)+(1-z)^2(1+z)\ln(1+z)) $$

显然它是微分有限的，也就具有整式递推式。不过整体的递推式显而易见地会很长。通过把式子拆开计算，可以得到空间复杂度 $\Theta(1)$、时间复杂度 $\Theta(n)$；或空间复杂度 $\Theta(\sqrt n)$，时间复杂度 $\Theta(\sqrt n \log n)$ 的做法（不过也都非常麻烦就是了）。

出题人比较卡常，给个参考代码吧：

#define uint unsigned int
#define ull unsigned long long

uint inv[N],f[N],g[N];
uint n,ans,p,fac;

inline uint add(uint x,uint y){ return x+y>=p?x+y-p:x+y; }
inline uint dec(uint x,uint y){ return x<y?x+p-y:x-y; }

inline uint power(uint a,uint t){
    uint res = 1;
    while(t){
        if(t&1) res = (ull)res*a%p;
        a = (ull)a*a%p;
        t >>= 1;
    }
    return res;
}

int main(){
    scanf("%u%u",&n,&p);
    inv[1] = 1;
    for(int i=2;i<=n+1;++i) inv[i] = (ull)(p-p/i)*inv[p%i]%p;
    f[0] = 1;
    for(int i=1;i<=n;++i) f[i] = p-(ull)f[i-1]*inv[i+1]%p;
    fac = (n&1)?f[n-1]:p-f[n-1];
    for(int i=1;i<=n;++i) f[i] = add(f[i],f[i-1]);
    for(int i=1;i<=n;++i) f[i] = add(f[i],f[i-1]);
    for(int i=1;i<=n;++i) g[i] = (i&1)?inv[i]:p-inv[i];
    for(int i=n;i>1;--i) g[i] = dec(dec(g[i],g[i-2]),inv[i]);
    g[1] = dec(g[1],1);
    for(int i=n;i>0;--i) g[i] = (g[i]+p-g[i-1])%p;
    g[2] = (g[2]+2)%p,g[3] = (g[3]-1+p)%p;
    for(int i=0;i<=n;++i) ans = (ans + (ull)f[i]*g[n-i])%p;
    ans = (ull)ans*power(fac,p-2)%p;
    printf("%u",ans);
    return 0;
}