大水题。 主要是记一下错排的公式。顺便水一水 递推公式： fi=(i−1)(fi+fi−1) 推导过程大概是，考虑数字 i , 它有 i−1 种可能的位置，设 i 在位置 k ,则数字 k 可能放在 位置 i 或不放在位置 i 。放在位置 i , 则其他方案数等价于 fi−2 ，否则等价于 fi−1 。 还有一个公式就是 O(n) 的容斥了： fn=∑i=0(−1)i(ni)(n−i)! 。
#include<cstdio> #include<algorithm> using namespace std; typedef long long LL; const int maxn=1000005,MOD=1e9+7,N=1000000; typedef long long LL; int _test,n,m; LL f[maxn],fac[maxn],fac_inv[maxn],inv[maxn]; LL C(int n,int m){ return fac[n]*fac_inv[m]%MOD*fac_inv[n-m]%MOD; } int main(){ freopen("loj2034.in","r",stdin); freopen("loj2034.out","w",stdout); fac[0]=1; for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i%MOD; inv[1]=1; for(int i=2;i<=N;i++) inv[i]=(LL)(MOD-MOD/i)*inv[MOD%i]%MOD; fac_inv[0]=1; for(int i=1;i<=N;i++) fac_inv[i]=fac_inv[i-1]*inv[i]%MOD; f[0]=1; f[1]=0; for(int i=2;i<=N;i++) f[i]=((LL)i-1)*(f[i-1]+f[i-2])%MOD; scanf("%d",&_test); while(_test--){ scanf("%d%d",&n,&m); printf("%d\n",C(n,m)*f[n-m]%MOD); } return 0; }