本文共 4888 字，大约阅读时间需要 16 分钟。

题目

思路

错排是众所周知的。这是一个计数，求一一对应关系 $y=f(x)$ 的数量。该函数满足 $\forall x\in [1,n]\cap \mathbb{Z},f(x)\ne x$ 。记录为 $d(n)$ 。

我们用容斥去计算。枚举至少有多少个 $x$ 满足 $f(x)$ ，就可以写出

$$\begin{array}{rl}d(n)& =\sum _{i=0}^n(-1{)}^i(\genfrac{}{}{0ex}{}{n}{i})(n-i)!\\ & =\sum _{i=0}^n(-1{)}^i\cdot \frac{n!}{i!\cdot (n-i)!}\cdot (n-i)!\\ & =\sum _{i=0}^n\frac{(-1{)}^i\cdot n!}{i!}\\ & =\sum _{i=0}^n(-1{)}^i\prod _{j=i+1}^{n}j\end{array}$$

然后用倒数第二行的公式，可以看出递推式 $$d(n)=n\cdot d(n-1)+(-1{)}^n$$

$n$ 是用来补充 $n!$ 中相较于 $d(n-1)$ 即 $(n-1)!$ 的缺失，$(-1{)}^n$ 是加入的最后一项，就是 $i=n$ 的时候。

但是，这个递推是 $\mathcal{O}(n)$ 的，我没法优化它。想个办法，不如计算一下 $d(2p+1)\mathrm{m}\mathrm{o}\mathrm{d}p$ 的值。用公式的最后一行。注意到 ${\prod }_{j=i+1}^{n}j$ 这一项在 $i+1\le 2p$ 即 $i\le 2p-1$ 的时候，都包含了 $2p$ 这一因数，故在取模意义下为零。我们只剩下两项， i ∈ { 2 p , 2 p + 1 } i\in\{2p,2p+1\} i∈{ 2p,2p+1} 的贡献，单独算。

$$d(2p+1)\equiv -1\cdot (2p+1)+1\times 1\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

毕竟 $2p+1\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$ 。然鹅，我们知道 $d(1)=0=d(2p+1)$，这时候我们可以用递推公式计算 $d(2p+2)$ 了。

$$\begin{array}{rl}d(2p+2)& =(2p+2)\cdot d(2p+1)+(-1{)}^{2p+2}\\ & \equiv 2\cdot d(1)+(-1{)}^2(\mathrm{m}\mathrm{o}\mathrm{d}p)\\ & =d(2)\end{array}$$

注意到了吗？两个相乘的数字 $(2p+k+1)$ 和 $d(2p+k)$ 在模 $p$ 意义下同时出现了循环。

以此类推，$d(2p+3)\equiv d(3),d(2p+4)\equiv d(4),\dots ,d(2p+k)\equiv d(k)$ 都是成立的。

最后的结论就是，$d$ 出现了循环。我们有 $$d(2p+k)=d(k)(k>0)$$

注意 $d(2p)\ne d(0)$ 。所以不要直接取模 $2p$ 。

现在我们只需要用 $\mathcal{O}(p)$ 的时间计算了。然后这道题要求 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)d(n-k)\mathrm{m}\mathrm{o}\mathrm{d}m$ ，就很简单了呗。组合数用 $Lucas$ 求解。

代码

#include <cstdio>#include <iostream>#include <vector>using namespace std;typedef long long int_;inline int readint(){       int x; scanf("%d",&x); return x;}inline int qkpow(int base,int q,int Mod){       int ans = 1; base %= Mod;    for(; q; q>>=1,base=1ll*base*base%Mod)        if(q&1) ans = 1ll*ans*base%Mod;    return ans;}int exgcd(int a,int b,int_ &x,int_ &y){       if(b == 0){           x = 1, y = 0; return a;    }    int d = exgcd(b,a%b,y,x);    y -= (a/b)*x; return d;}int getInv(int x,int p){       int_ res, useless;    if(exgcd(x%p,p,res,useless) != 1)        return -1; // impossible    return (res%p+p)%p;}int CRT(int n,int m[],int c[]){       int M = 1, ans = 0;    for(int i=1; i<=n; ++i) M *= m[i];    for(int i=1; i<=n; ++i){           int tmp = M/m[i];        tmp *= getInv(tmp,m[i]);        ans = (ans+1ll*tmp*c[i])%M;    }    return ans;}int function(int n,int p,int pk){       int res = 1; if(n < 2) return 1;    if(n >= pk){           for(int i=2; i<=pk; ++i)            if(i%p != 0)                res = 1ll*res*i%pk;        res = qkpow(res,n/pk,pk);    }    for(int i=2; i<=n%pk; ++i)        if(i%p != 0)            res = 1ll*res*i%pk;    return 1ll*res*function(n/p,p,pk)%pk;}int calc(int n,int p){       if(n < p) return 0; return n/p+calc(n/p,p);}int exLucas(int n,int m,int p,int pk){       int pt = calc(n,p)-calc(m,p)-calc(n-m,p);    int jb = function(n,p,pk); // zxy orz    jb = 1ll*jb*getInv(function(m,p,pk),pk)%pk;    jb = 1ll*jb*getInv(function(n-m,p,pk),pk)%pk;    return 1ll*jb*qkpow(p,pt,pk)%pk;}int mods[50], yu[50];int Lucas(int n,int m,int p){       int cnt = 0;    for(int i=2,j; 1ll*i*i<=p; ++i){           if(p%i != 0) continue;        for(j=1; p%i==0; j*=i) p /= i;        mods[++ cnt] = j;        yu[cnt] = exLucas(n,m,i,j);    }    if(p != 1){           mods[++ cnt] = p;        yu[cnt] = exLucas(n,m,p,p);    }    return CRT(cnt,mods,yu);}signed main(){       for(int T=readint(),kase=0; T; --T){           int n = readint(), m = readint();        int p = readint(), cp = 1;        if(n < m or p == 1){               printf("Case %d: 0\n",++kase);            continue;        }        int t = (n-m-1)%(p<<1)+1;        for(int i=1; i<=t; ++i)            cp = (1ll*cp*i+1-(i<<1&2))%p;        if(cp < 0) cp += p;        printf("Case %d: %lld\n",++kase,1ll*Lucas(n,m,p)*cp%p);    }    return 0;}