P4071 [SDOI2016]排列计数
题目描述
求有多少种长度为 n 的序列 A，满足以下条件：
1 ~ n 这 n 个数在序列中各出现了一次
若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的
满足条件的序列可能很多，序列数对 (10^9+7) 取模。
输入格式
第一行一个数 T，表示有 T 组数据。
接下来 T 行，每行两个整数 n、m。
输出格式
输出 T 行，每行一个数，表示求出的序列数
输入输出样例
输入 #1
5
1 0
1 1
5 2
100 50
10000 5000
输出 #1
0
1
20
578028887
60695423
说明/提示
测试点 1 ~ 3： $ T = 1000(，)n leq 8(，)m leq 8$；
测试点 4 ~ 6： $ T = 1000(，)n leq 12(，)m leq 12$；
测试点 7 ~ 9： $ T = 1000(，)n leq 100(，)m leq 100$；
测试点 10 ~ 12：$ T = 1000(，)n leq 1000(，)m leq 1000$；
测试点 13 ~ 14：$ T = 500000(，)n leq 1000(，)m leq 1000$；
测试点 15 ~ 20：$ T = 500000(，)n leq 1000000(，)m leq 1000000$。
【思路】
组合数学 / 错排
【题目大意】
a[i]在i的位置上面是稳定的
求有m个数是稳定的序列有多少个
【题目分析】
求符合条件序列的个数
符合条件序列可以先只看那稳定的数
一个序列中只有m个数是稳定的
其他的都是稳定的
那么稳定的数组合方式就是n个数里面取m个
因为如果稳定那一个数只对应一个位置
所以不存在顺序这一说，所以就是 (C_n^m)
知道了稳定数的组合方式
拿在看看除了这些稳定数之外数的组合方式
其他的数都是不在自己的位置上面的
也就是错排
直接用错排求出n-m（这里是减号下同下下同）个人错排方法的数量就好了
因为一种稳定数对应n-m个人的错排方式
所以数量数就是 (C_n^m) * (n-m)个人的错排方式
【存在的问题】
1.因为n和m的数据范围都是小于等于1e6
不是很小,而且T很大，
所以每次T 不能都单独求C和错排次数了
这样一定会超时
2.因为这道题中有取模运算
而递推求组合数只能过2000所以用这个阶乘求组合数就是必然的了
那么就要用到除法
而取模运算中不能用除法
【优化】
1.针对问题1
多次求解会超时
那就先预处理出来所有的阶乘和i个人的错排方式
到时候O(1)查询就好了
2.针对问题2
既然不能用除法那就用乘法
用逆元来代替除法就可以啦
求逆元因为模数是质数
所以可以用费马小定理求
费马小定理求逆元详见
这里
【完整代码】
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int k = 1e9 + 7;
const int Max = 1000005;
int d[Max];
int f[Max];
int inv[Max];
int p(int a,int b)
{
int ans = 1;
while(b)
{
if(b & 1)
ans = ans * a % k;
b >>= 1;
a = a * a % k;
}
return ans;
}
signed main()
{
d[0] = 1,d[2] = 1;
for(register int i = 3;i <= 1000000;++ i)
d[i] = (i - 1) * (d[i - 1] + d[i - 2]) % k;
f[0] = 1,f[1] = 1;
for(register int i = 2;i <= 1000000;++ i)
f[i] = f[i - 1] * i % k;
inv[0] = p(f[0],k - 2);
for(register int i = 1;i <= 1000000;++ i)
inv[i] = p(f[i],k - 2) % k;
int t;
cin >> t;
while(t --)
{
int n,m;
scanf("%lld%lld",&n,&m);
//c(n,m) * d(n-m)
//n!/m!(n - m)! * d[n-m]
printf("%lld
",(f[n] * inv[m] % k * inv[n-m] % k * d[n-m]) % k);
}
return 0;
}