排列计数

---

题目链接：暂无

---

题目描述

求有多少种长度为 n 的序列 A，满足以下条件：

• 1∼n 这 n 个数在序列中各出现了一次；
• 若第 i 个数 Ai 的值为 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

解释

遇到这道题两次了
我觉得这道题的知识点非常有趣
首先，错排公式我在高中数学中就接触过，就相当于n个人各有一个座位，每个人都坐在别人的位置上的种数。
前几项是0 1 2 9 44 265
我对这个数列非常喜欢
2=(0+1)*2
9=(1+2)*3
44=(2+9)*4
265=(9+44)*5
a[n]=(a[n-1]+a[n-2])*(n-1)
至于通项公式也可以推一推或者上网搜一搜
可以看出
这道题的意思就是其中的m个数在原来的位置，剩下的(n-m)个数进行了错排
也就是
C(m,n)*a[n-m]
但这个数据很大，题目说需要取模
那我们很容易就把阶乘和错排的数组边乘边取模给做完了
C(m,n)中有一步除以(n-m)!的过程该怎么办呢？
这时我们想到可以求逆元
费马小定理是指
如果p是一个质数，而整数a不是p的倍数，则有a^(p-1) ≡ 1 (mod p)
由费马小定理可知
a * a ^ (p-2) ≡ 1 (mod p)
a ^ (p-2) ≡ 1/a (mod p)
因此可知逆元就是a^(p-2)%p
因此我们做了一个存放逆元的数组
是不是直接输出就好了呢？
我们试了一下发现TLE
因此快快用上快速幂模板来加快我们求逆元的速度
快速幂这个算法体现了分治的思想
把每次的乘方拆成两半来解决
速度一下子就减了不少
我们试着交了一下，AC！

代码部分

#include<bits/stdc++.h>
using namespace std;
const long long k=1e9+7;
long long cp[1000020],jc[1000020],ny[1000020];
int f(long long a,long long b)   //快速幂模板
{
	long long ans = 1;
	while (b>0) {
		if (b%2==1) ans=ans*a%k;
		b/=2;
		a=a*a%k;
	}
	return ans;
}
int main()
{
	cp[0]=1,cp[2]=1;
	for (int i=3;i<=1000000;i++)
		cp[i]=(i-1)*(cp[i-1]+cp[i-2])%k;//cp即由错排公式从第0~n个元素组成的数组
	jc[0]=1,jc[1]=1;
	for (int i=2;i<=1000000;i++)
		jc[i]=jc[i-1]*i%k;//jc即阶乘
	ny[0] =f(jc[0],k - 2);
	for (int i=1;i<=1000000;i++)
		ny[i]=f(jc[i],k-2)%k;//ny即逆元
	int t;
	cin>>t;
	for (int i=1;i<=t;i++) {
		long long n,m;
		cin>>n>>m;
		cout<<(jc[n]*ny[m]%k*ny[n-m]%k*cp[n-m])%k<<endl;
	}
	return 0;
}

收获

• 学到了快速幂模板
• 学到了用费马小定理推得的逆元，成功解决了除法取模的问题。