计算小练习 14：P7120 Chino 的比赛

· · 题解

首先要知道一点：\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;
}