【[SDOI2016]排列计数】

一眼题，答案就是(C_m^m*d_{n-m})

就是从(n)个中选取(m)个在位，剩下的错排，之后就是乘法原理了

但是我发现我的错排公式竟然一直不会推

这个递推式很简单，就是(d[1]=0,d[2]=1,d[n]=(n-1)*(d[n-2]+d[n-1))

其实是这样推出来的

我们从(n)个元素错排开始考虑，我们特殊判断一下第一个位置不能填(1)，但是从(2)到(n)这(n-1)个数可以随便选，于是有(n-1)种可能

假设第一次放的的元素是(k)

之后剩下的就是

[1 2 3 ...k-1 k+1 k+2 k+3...n ]

我们可以将这些从小到大对应到(1)到(n-1)，之后剩下的继续错排就好啦

于是就是(d[n-1])

但是我们这个样子本质上是使得(k)那个位置不能放(k+1)的（因为(k+1)在去掉(k)之后是第(k)小的），于是我们还可以让(k)这个位置放(k+1)，之后剩下的继续错排，于是就是(d[n-2])

加法原理这两种不同的情况加起来，再利用乘法原理第一位上有(n-1)种选择

于是就有(d[n]=(n-1)*(d[n-2]+d[n-1]))

发现luogu日报里竟然又讲错排那就在这里收藏一下

小学生都能看懂的错排问题解析

这道题的代码

#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define LL long long
#define maxn 1000005
const int mod=1e9+7;
LL fac[maxn],d[maxn];
int T;
LL x,y;
inline LL read()
{
	char c=getchar();
	LL x=0;
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9')
	  x=(x<<3)+(x<<1)+c-48,c=getchar();
	return x;
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{
	if(!b) return x=1,y=0,a;
	LL r=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return r;
}
inline LL C(LL n,LL m)
{
	LL r=exgcd(fac[m]*fac[n-m]%mod,mod,x,y);
	x=(x%mod+mod)%mod;
	return fac[n]*x%mod;
}
int main()
{
	T=read();
	fac[0]=1,fac[1]=1;
	for(re int i=2;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
	d[0]=1,d[1]=0,d[2]=1;
	for(re int i=3;i<=1000000;i++) d[i]=(d[i-1]+d[i-2]%mod)*(i-1)%mod;
	LL n,m;
	while(T--)
	{
		n=read(),m=read();
		printf("%lld",C(n,m)*d[n-m]%mod);
		putchar(10);
	}
	return 0;
}