错排&排列计数题解

不要我为啥更这题,因为这种题,代码简单,思路简单.
dp:
先讲讲错排公式,D[1]=0,D[2]=1.这个是初始值.
下面讲讲转移方程:D[i]=(n-1)*(D[i-1]+D[i-2]).
考虑把第n个元素放到任意一个地方,那就有n-1种放法,假定我放的位子为k,那么我k就有两种放法,第一种是放到n的位子,那就是D[i-2],第二种是不放到n的位子,那就相当于i-1的一个错排,D[i-1].

数学:(容斥原理)总方案数为n!,放对一个位子的方案数是C(n,1)An-1,其中必定包含放对两个的方案数,C(n,2)An-2...容斥下去即可得到通项公式.

反演暂时不熟悉,以后再更~

代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=1e6+5;
ll D[N],fact[N];
ll qp(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

inline ll C(ll n,ll m)
{
    ll res=fact[n];
    return res*qp(fact[m],mod-2)%mod*qp(fact[n-m],mod-2)%mod;
}

void init()
{
    for(int i=3;i<=N-5;i++)
    {
        D[i]=(i-1)*(D[i-2]+D[i-1])%mod;
    }
    fact[1]=1;fact[0]=1;
    for(int i=2;i<=N-5;i++)
    {
        fact[i]=i*fact[i-1]%mod;
    }
}

int main()
{
    D[1]=0;D[2]=1;D[0]=1;
    init();
    int T;
    ll n,m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&m);
        ll ans=D[n-m]*C(n,m)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}