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

· · 题解

没思路？我们来找规律！
比如一个n=5的排列，我们假设m=2也就是说，我们其实已经确定了排列种某些位置的值，就这个例子来说：

12???$ $1?3??$ $1??4?$ $1???5$ $?23??$ $?2?4?$ $?2??5$ $??34?$ $??3?5$ $???45

共10种，很容易发现其实就是C_n^m，那么其中的问号又多少种排列呢？

没思路？我们再来找规律！
我们设D_i为i个?的可能的排列数，显然，D_1=0 D_2=1
接着我们来看下D_3，可以有312,231
如果我们继续找下去的话，容易出错，所以我们现在来找找规律（灵魂画师）。
就拿D_4来说，上面的是数，下面的是位置，首先，1不能放到1号位，而且放到2，3，4上对于递推是等价的，于是他别无选择地放到了其他地方（假设是2号位）

然后我们假设2放到1号位上去，剩下的3，4正好是D_2

但2怎么可能只有放在1号位上的命运呢？它还可以不放到1号位，咦？我们之前说，i不能放到i号位，那么既然2不放到1号位，那么1号位在这里是不是等价于2号位呢？没错！
而之前的“万恶之源”数字1，它有n-1种放法，所以我们就大胆猜测：D_n=(n-1)(D_{n-1}+D_{n-2})
严谨的证明还请大家自己百度
然后我们就愉快地输出C_n^m\times D_{n-m}就好啦
其他知识点比如说逆元求组合数（费马小定理）还请大家自行了解

欢迎来我博客玩~

代码

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int MAXN=1000005,mod=1000000007;
ll f[MAXN],inv[MAXN],d[MAXN];
int t;

ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=a*ans%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

void prework(){
    f[0]=1;
    for(int i=1;i<MAXN;i++){
        f[i]=f[i-1]*i%mod;
        inv[i]=qpow(f[i],mod-2);
    }
    d[1]=0,d[2]=1,d[3]=2;
    for(int i=4;i<MAXN;i++){
        d[i]=(i-1)*(d[i-1]+d[i-2])%mod;
    }
}

int main(){
    cin>>t;
    prework();
    for(int i=1;i<=t;i++){
        ll n,m;
        scanf("%lld%lld",&n,&m);
        if (n - m == 1) printf("0\n");
        else if (m == n) printf("1\n");
        else if (m == 0) printf("%lld\n",d[n]);
        else {
            printf("%lld\n",f[n] * inv[m] % mod * inv[n-m] % mod * d[n-m] % mod);
        }
    }
    return 0;
}