题目描述
求有多少种 1 到 n 的排列 a,满足序列恰好有 m 个位置 i,使得 。
答案对 取模。
输入格式
本题单测试点内有多组数据。
输入的第一行是一个整数 T,代表测试数据的整数。
以下 T 行,每行描述一组测试数据。
对于每组测试数据,每行输入两个整数,依次代表 n 和 m。
输出格式
共输出 T 行,对于每组测试数据,输出一行一个整数代表答案。
输入输出样例
输入 #1
5
1 0
1 1
5 2
100 50
10000 5000
输出 #1
0
1
20
578028887
60695423
说明/提示
数据规模与约定
本题共 20 个测试点,各测试点等分,其数据规模如下表。
测试点编号 | T = | 测试点编号 | T = | ||
---|---|---|---|---|---|
8 | |||||
12 | |||||
100 |
对于全部的测试点,保证 。
题目分析
不了解错排的同学可以先了解下错排。
可发现该问题是错排的一个变形。题目要求的是有"m 个位置 i,使得 。"。相当于从n个数中,挑m个位置不变动,剩下的进行错排。
就可得到计算公式: 。
本题中的范围很大,首先利用同余性质,预处理求出阶乘、错排列取余后的内容。再利用乘法逆元,将转成 ,再利用同余性质进行处理。
逆元则可利用费马小定理进行求解:,此时逆元x可取为。
预处理
jc[0]=1;jc[1]=1,jc[2]=2;
d[0]=0;d[1]=0;d[2]=1;
for(int i=3;i<=N-5;i++){
d[i]=(i-1)*(d[i-2]+d[i-1])%M;
jc[i]=jc[i-1]*i%M;
}
快速幂
ll mypow(ll x,ll n,int M){
if(n==0) return 1%M;
ll tmp=mypow(x,n/2,M)%M;
if(n&1) return tmp*tmp%M*x%M;
else return tmp*tmp%M;
}
代码实现
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int M=1e9+7;
const int N=1e6+5;
ll mypow(ll x,ll n){//快速幂 求 x的n次幂
if(n==0) return 1%M;
ll tmp=mypow(x,n/2)%M;
if(n&1) return tmp*tmp%M*x%M;
else return tmp*tmp%M;
}
ll jc[N];//jc[x] = x!
ll d[N];//d[x] = x个元素的错排列数
ll C(int n,int m){//求组合C(n,m)
return jc[n]*mypow(jc[m]*jc[n-m]%M,M-2)%M;
}
int main(){
int t,n,m;
scanf("%d",&t);
//预处理 阶乘 和 错排列数
jc[0]=1;jc[1]=1,jc[2]=2;
d[0]=0;d[1]=0;d[2]=1;
for(int i=3;i<=N-5;i++){
d[i]=(i-1)*(d[i-2]+d[i-1])%M;
jc[i]=jc[i-1]*i%M;
}
while(t--){
scanf("%d%d",&n,&m);
if(n==m) printf("1\n");
//C(n,m)*D(n-m)
else printf("%lld\n",C(n,m)*d[n-m]%M);
}
return 0;
}