求有多少种长度为 n 的序列 A，满足以下条件： 1 ~ n 这 n 个数在序列中各出现了一次 若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的 满足条件的序列可能很多，序列数对 10^9+7 取模。
需要用到一个错位排列公式：\[f_n=n \times f_{n-1}+(-1)^n\] \(f_n\)代表数组长度为\(n\)时的错位排列数，初始值\(f_0=1\) 结果显然就是\[\binom{m}{n} \times f_{n-m}\] 用逆元预处理一下需要的值就可以了
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int ReadInt()
{
int x=0,f=1; char ch=getchar();
while (ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
LL inv[1000010]={};
LL p;
LL f[1000010]={};
LL fz[1000010]={};
LL fm[1000010]={};
int main()
{
p=1e9;
p+=7;
inv[0]=inv[1]=1;
for(int i=2;i<=1000000;i++) inv[i]=((p-p/i)*inv[p%i])%p;
f[0]=1;
for(int i=1;i<=1000000;i++)
{
f[i]=i*f[i-1];
if(i%2==1) f[i]--;
else f[i]++;
f[i]%=p;
}
fz[0]=1;
fm[0]=1;
for(int i=1;i<=1000000;i++)
{
fz[i]=fz[i-1]*i;
fz[i]%=p;
fm[i]=fm[i-1]*inv[i];
fm[i]%=p;
}
int T;
LL ans;
int n,m;
T=ReadInt();
while(T--)
{
ans=1ll;
n=ReadInt();
m=ReadInt();
ans*=f[n-m];
ans%=p;
ans*=fz[n];
ans%=p;
ans*=fm[m];
ans%=p;
ans*=fm[n-m];
ans%=p;
printf("%lld\n",ans);
}
return 0;
}
|