【题解】排列计数

题目描述

求有多少种 1 到 n 的排列 a，满足序列恰好有 m 个位置 i，使得 $a_i = i$ 。

答案对 $10^9 + 7$ 取模。

输入格式

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

输入的第一行是一个整数 T，代表测试数据的整数。

以下 T 行，每行描述一组测试数据。

对于每组测试数据，每行输入两个整数，依次代表 n 和 m。

输出格式

共输出 T 行，对于每组测试数据，输出一行一个整数代表答案。

输入输出样例

输入 #1

输出 #1

说明/提示

数据规模与约定

本题共 20 个测试点，各测试点等分，其数据规模如下表。

测试点编号	T =	$n, m \leq$	测试点编号	T =	$n, m \leq$
$1\sim 3$	$10^3$	8	$10 \sim 12$	$10^3$	$10^3$
$4 \sim 6$	$10^3$	12	$13 \sim 14$	$5 \times 10^5$	$10^3$
$7 \sim 9$	$10^3$	100	$15 \sim 20$	$5 \times 10^5$	$10^6$

对于全部的测试点，保证 $1 \leq T \leq 5 \times 10^5，1 \leq n \leq 10^6，0 \leq m \leq 10^6$ 。

题目分析

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

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

就可得到计算公式： $C_n^m\cdot D(n-m)$ 。

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

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

逆元则可利用费马小定理进行求解： $a^{p-1} \equiv1(mode\ p)$ ，此时逆元x可取为 $a^{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.

WRONG ANSWER