题目描述

求有多少种长度为 n 的序列 A，满足以下条件：

1、1 ~ n 这 n 个数在序列中各出现了一次。

2、若第 i 个数 A[i] 的值为 i，则称 i 是稳定的，序列恰好有 m 个数是稳定的。

由于满足条件的序列可能很多，所以请你将序列数对 109+7 取模后输出。

输入格式
第一行一个数 T，表示有 T 组数据。

接下来 T 行，每行两个整数 n、m。

输出格式
输出 T 行，每行一个整数，表示求出的序列数对 109+7 取模后的值。

数据范围
T≤500000,n≤1000000,m≤1000000

样例

输入样例
5
1 0
1 1
5 2
100 50
10000 5000

输出样例
0
1
20
578028887
60695423

思路

根据题目的描述，我们可以知道在这n个数当中已经有m个数已经确定好了它的位置。所以我们先从从n个数中任取m个数。
那剩下的n-m个数，根据题意是需要错排的。我们可以根据错排公式f[i]=(n-1)(f[i-1]+f[i-2])得到这n-m个数的排列种数。
/错排公式的证明：
为求其递推关系，分两步走：
第一步，考虑第n个元素，把它放在某一个位置,比如位置k，一共有n-1种放法；
第二步，考虑第k个元素，这时有两种情况：（1）把它放到位置n，那么对于除n以外的n-1个元素，由于第k个元素放到了位置n，所以剩下n-2个元素的错排即可，有f[i-2]种放法；（2）第k个元素不放到位置n，这时对于这n-1个元素的错排，有f[i-1]种放法。*/
只需要把这两部分相乘便可以得到最后的答案。

C++ 代码

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=1e6+5;
ll d[N],f[N],inv[N],n,m;
ll qpow(ll a, ll b){
    ll c=1;
    for (;b;b>>=1,a=a*a%mod)
        if (b & 1)
        c=c*a%mod;
    return c;
}
int main(){
    int t,i,p=0;
    scanf("%d",&t);
    d[0]=1;
    d[1]=0;
    d[2]=1;
    f[0]=f[1]=inv[0]=inv[1]=1;
    f[2]=2;
    inv[2]=qpow(2,mod-2);
    for (i=3;i<=N;++i)
    {
        d[i]=(d[i-1]+d[i-2])%mod*(i-1)%mod;
        f[i]=f[i-1]*i%mod;
        inv[i]=qpow(f[i],mod-2);
    }
    for (i=1;i<=t;++i)
    {
        scanf("%d%d",&n,&m);
        printf("%lld\n", f[n]*inv[n-m]%mod*inv[m]%mod*d[n-m]%mod);
    }
    return 0;
}