摘要:错排问题

[SDOI2016]排列计数

题面

题目分析

如果读过《组合数学》的话,很容易就可以看出这是个错排问题.

错排问题的定义如下(直接抄书):

给定n元素集合X,它的每一个元素都有一个特定的位置,而现在要求求出集合X的排列中没有一个元素在它指定位置上的排列的数目.

用$D_n$表示$\{1,2,…,n\}$错排数目,根据容斥原理可以得到$D_n$的公式(证明见《组合数学》第五版108页):

$D_n = n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+…+(-1)^n\frac{1}{n!})$

还可以通过$D_1=0$,$D_2=1$出发,递推得:

$D_n=(n-1)(D_{n-1}+D_{n-2}) ~ (n=3,4,5,…)$

本人能力有限,只能做个初步的介绍,现在回到这道题上,题意是让长度为n的序列有且仅有有m个数在原本的位置上.

所以其他的n-m个数就一定不在原本的位置上,这样的情况数就是n-m的错位排列数目,即$D_{n-m}$.

然后是这m个在原本位置上的数,这样m个数可以在序列中任取,情况数就是$C_n^m$,因为题目要求模一个质数,直接lucas求即可.

根据乘法原理,$D_{n-m}*C_n^m$就是答案了.

特判一下n=m的情况,答案为1,因为只有原序列满足答案.

预处理一下阶乘和$D_n$就可以了,之前很憨地暴算阶乘t掉了. /kk

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include "iostream"
#include "cstdio"
#include "cstring"
#include "cstdlib"
#include "cctype"
#include "cmath"
#include "iomanip"
#include "algorithm"
#include "time.h"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define lxl long long
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
const lxl maxn=1000010,p=1e9+7;
lxl T,n,m;
lxl d[maxn],cm[maxn];
inline lxl read()
{
char c=getchar();
lxl f=1,x=0;
for(;!isdigit(c);c=getchar())(c=='-')&&(f=-1);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f*x;
}
inline lxl FastPow(lxl a,lxl b,lxl mod)
{
lxl sum=1;
for(;b;b>>=1,a=a*a%mod)(b&1)&&(sum=sum*a%mod);
return sum;
}
inline lxl inv(lxl a,lxl p)
{
return FastPow(a,p-2,p);
}
inline lxl C(lxl n,lxl m,lxl p)
{
// if(m>n)return 0;
// lxl up=1,down=1;
// for(R int i(n-m+1);i<=n;++i)up=up*i%p;
// for(R int i(1);i<=m;++i)down=down*i%p;
// return up*inv(down,p)%p;
return (cm[n]*inv(cm[m]*cm[n-m]%p,p)%p);
}
lxl Lucas(lxl n,lxl m,lxl p)
{
if(m==0)return 1;
return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}
inline void prework()
{
d[1]=0,d[2]=1,cm[1]=1,cm[2]=2;
for(R int i(3);i<maxn;++i)d[i]=(i-1)*(d[i-1]+d[i-2])%p,cm[i]=cm[i-1]*i%p;
}
int main(void)
{
prework();
T=read();
while(T--)
{
n=read(),m=read();
if(m==n)
{
printf("1\n");
continue;
}
printf("%lld\n",Lucas(n,m,p)*d[n-m]%p);
}
return 0;
}