「SDOI2016」排列计数tj(附压行代码)

Funny-cat / 2023-08-24 / 原文

现在求有多少种长度为 n 的序列 A，满足以下条件：
1 ~ n 这 n 个数在序列中各出现了一次
若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的
满足条件的序列可能很多，序列数对 10^9+7 取模。

输入

第一行一个数 T，表示有 T 组数据。
接下来 T 行，每行两个整数 n、m。

输出

输出 T 行，每行一个数，表示求出的序列数。

思路

Tap1.（Wrong）

诶？有 m 个数待在自己的位置上，即这个数是稳定的。

不就是\(C{^m_n}\)吗？？？直接开搞

一顿乱码过后，喜提0 pts。。。

仔细分析后，发现是要求逆元，再次信心满满地乱码。。。

又爆0。。。

Tap2.

经过和同学的深度交流，正所谓"遇难则反"，我们找到了问题所在：

前者可以满足有m个数在自己的位置上，但不能保证剩下的数也一定不在自己的位置上，即使能保证，也不好求方案数

所以我们选择使用错位排序，先求出不满足的数的方案数和无限制的方案数，最后将前者与后者做减得出答案

错位排序的公式如下：

\(D{_1}=0\)

\(D{_2}=1\)

\(D{_i}=(D{_{i-1}}+D{_{i-2}})(i-1)\)

具体证明和推理请跳转至OI-WIKI或者OI-WIKI

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m;
const int Mod=1e9+7;
int d[1000005],inv[1000005],num[1000005];
int qpow(int a,int p,int mod)
{
	int t=1,x=a%mod;
	while(p)
	{
		if(p&1)
		{
			t=t*x%mod;
		}
		x=x*x%mod;
		p>>=1;
	}
	return t%mod;
}
void init()
{
	d[1]=0;
	d[2]=1;
	for(int i=3;i<=1000005;i++)
	{
		d[i]=(i-1)*(d[i-1]+d[i-2])%Mod;
	}
	inv[0]=num[0]=1;
	for(int i=1;i<=1000005;i++)
	{
		num[i]=(int)num[i-1]*i%Mod;
		inv[i]=(int)inv[i-1]*qpow(i,Mod-2,Mod)%Mod;
	}
}
signed main()
{
	init();
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		if(n==m)
		{
			cout<<"1\n";
			continue;
		}
		int node=(int)(num[n]*inv[m]%Mod*inv[n-m]%Mod);
		cout<<(int)(node*d[n-m]%Mod)<<endl;
	}
	return 0;
}