题目描述

求有多少种 1 到 n 的排列 a,满足序列恰好有 m 个位置 i,使得 ai=ia_i = i

答案对 109+710^9 + 7 取模。

输入格式

本题单测试点内有多组数据

输入的第一行是一个整数 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 = n,mn, m \leq 测试点编号 T = n,mn, m \leq
131\sim 3 10310^3 8 101210 \sim 12 10310^3 10310^3
464 \sim 6 10310^3 12 131413 \sim 14 5×1055 \times 10^5 10310^3
797 \sim 9 10310^3 100 152015 \sim 20 5×1055 \times 10^5 10610^6

对于全部的测试点,保证 1T5×1051n1060m1061 \leq T \leq 5 \times 10^5,1 \leq n \leq 10^6,0 \leq m \leq 10^6

题目分析

不了解错排的同学可以先了解下错排

可发现该问题是错排的一个变形。题目要求的是有"m 个位置 i,使得 ai=ia_i = i。"。相当于从n个数中,挑m个位置不变动,剩下的进行错排。

就可得到计算公式:CnmD(nm)C_n^m\cdot D(n-m)

Cnm=n!m!(nm)!C_n^m=\frac{n!}{m!(n-m)!}

本题中n,mn,m的范围很大,首先利用同余性质,预处理求出阶乘、错排列取余后的内容。再利用乘法逆元,将a/ba/b转成a×b1a\times b^{-1} ,再利用同余性质进行处理。

逆元则可利用费马小定理进行求解:ap11(mode p)a^{p-1} \equiv1(mode\ p),此时逆元x可取为ap2%pa^{p-2}\%p

预处理

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;
}

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)