【[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;

}