题解 P4071 【[SDOI2016]排列计数】

· · 题解

那么这道题是一个非常棒的错排问题的入门题

对于这类求方案数的问题的话

关键是不重不漏……，对于这道题可以使用枚举“区分点”的方法

也就是说，我们枚举的“区分点”，必须要让任意两个方案，只要区分点不同，那么这两个方案就不同

那么对于这道题来讲，就是如果连稳定的数字都不一样了，这两个方案就肯定不同了，那这样的话，那些数字是稳定的就是所谓的区分点所以我们可以先钦定到底哪m个数是稳定的，一共有C_{n}^{m}种方案

下面在钦定了这m个数字稳定之后，其他的数字必须全部不稳定，这个问题被称为全错排问题，也就是说，没有一个数字是稳定的序列个数

设D_{n}为长度为n的全错排序列个数那么的话我们呢会有一个一个递推式子

假设我们现在要求长度为n的错排方案数

那么我们呢就枚举第n个位置放在那个位置数上

显然一共有n-1个位置可以放，并且肯定有一个数t放在了第n个位置上

假设n放在了t位置上，那么剩下的序列必须构成一个长度为n-2的错排列

假设n没有放在t位置上，那么剩下的序列必须构成一个长度为n-1的错排列(因为n不能放在t上了)

上述两种情况是互斥的，因此可以直接加起来

枚举n放在那个位置是独立的，因此可以和上述两种情况乘起来

因此我们就有了一个极吼的递推公式

D_{n}=(n-1)(D_{n-1}+D_{n-2})

然后我们最后输出C_{n}^{m}×D_{n-m}就好啦

关于求组合数的问题可以打表逆元和阶乘，然后我们就可以O(10^{6})预处理 然后O(1)回答询问啦~

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e6+10;typedef long long ll;
const ll mod=1e9+7;ll inv[N];ll fac[N];ll ifac[N];ll d[N];int T;int n;int m;
int main()
{
    inv[1]=1;for(int i=2;i<=N-10;i++){inv[i]=(mod-mod/i)*inv[mod%i]%mod;}//打标逆元 
    fac[0]=1;for(int i=1;i<=N-10;i++){fac[i]=fac[i-1]*i%mod;}//打表阶乘 
    ifac[0]=1;for(int i=1;i<=N-10;i++){ifac[i]=ifac[i-1]*inv[i]%mod;}//打表逆元和阶乘 
    d[0]=1;d[1]=0;d[2]=1;for(ll i=3;i<=N-10;i++){d[i]=(i-1)*(d[i-1]+d[i-2])%mod;}//打表错排 
    scanf("%d",&T);
    for(int i=1;i<=T;i++)
    {
        scanf("%d%d",&n,&m);
        printf("%lld\n",fac[n]*ifac[m]%mod*ifac[n-m]%mod*d[n-m]%mod);//输出答案 
    }return 0;//拜拜程序~ 
}