[SDOI2016] 排列计数（组合数学）

题目传送门

解题思路

可以先想想满足题目的序列是如何构造的？

1. 先从  个位置里选  个位置，使得这些位置上的 ，方案数为 。

2. 再将剩下的数错排。

于是，这又扯到了错排问题。

我们可以设  表示将  个元素错排的方案数。

我们可以将第  个数放在其他  个位置，剩余的错排；

也可以将第  个数与另外的  个数互换位置，剩余的错排；

所以最终得到：

方案数为 

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int q;
int f[1000001];
int g[1000001];
int mod=1e9+7;
int d[1000001];

int qpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
		{
			res*=a;
			res=(res+mod)%mod;
		}
		a*=a;
		a=(a+mod)%mod;
		b/=2;
		b=(b+mod)%mod;
	}
	return res%mod;
}
void init()
{
	f[0]=1;
	g[0]=1;
	d[2]=1;
	d[0]=1;
	for(int i=1;i<=1000000;i++)
	{
		f[i]=f[i-1]*i;
		f[i]=(f[i]+mod)%mod;
		g[i]=g[i-1]*qpow(i,mod-2)%mod;
		g[i]=(g[i]+mod)%mod;
		
	}
	for(int i=3;i<=1000000;i++)
	{
		d[i]=(i-1)%mod*(d[i-1]+d[i-2])%mod;
		d[i]=(d[i]+mod)%mod;
	}
}

int c(int n,int m)
{
	if(m>n)return 0;
	return f[n]%mod*g[m]%mod*g[n-m]%mod;
}
signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//	cout.tie(0);
	
	init();
	scanf("%lld",&q);
	int n,m;
	int ans;
	while(q--)
	{
		scanf("%lld%lld",&n,&m);
		ans=c(n,m);
		ans=(ans+mod)%mod;
		ans=ans*d[n-m]%mod;
		ans=(ans+mod)%mod;
		printf("%lld\n",ans);
	}
	return 0;
}