题意描述

给出两个正整数$n$ , $m$ , 求有多少种排列$A$满足以下条件：

排列由$1$到$n$构成，即$1~n$各在这个排列中出现一次
正好有$m$个位置满足$A[i] = i$

由于答案可能很大，因此你只需要给出答案对于$10^9 + 7$取模的结果即可。

输入格式

输入的第一行是一个整数 $t$，代表测试数据的组数

以下 $t$ 行，每行输入两个整数，依次代表 $n$ 和 $m$。

输出格式

输出共 $t$ 行。对于每组测试数据，输出一行一个整数代表答案。

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

数据范围和约定

测试点 1 ~ 3：$ T = 1000 $，$ n \leq 8 $，$ m \leq 8 $；
测试点 4 ~ 6：$ T = 1000 $，$ n \leq 12 $，$ m \leq 12 $；
测试点 7 ~ 9：$ T = 1000 $，$ n \leq 100 $，$ m \leq 100 $；
测试点 10 ~ 12：$ T = 1000 $，$ n \leq 1000 $，$ m \leq 1000 $；
测试点 13 ~ 14：$ T = 500000 $，$ n \leq 1000 $，$ m \leq 1000 $；
测试点 15 ~ 20：$ T = 500000 $，$ n \leq 1000000 $，$ m \leq 1000000 $。

分析

组合数学 + 错位排列

先看第一个条件，不难看出，这是个全排列。

再看第二个条件，考虑如何设计这样的数列。显然，我们可以在$n$个数中选择$m$个，使得他们满足第二个条件，而对于剩下的$n - m$个数直接进行错位排列即可。

综上，答案就是

$C_{n}^{m} \times D(n - m)$

顺便放出组合数公式与错排公式，没听说过的同学可以顺便补一下

$C_{n}^{m} = \frac{n!}{m!(n - m)!}$ $D(0) = 1 , D(2) = 1 , D(i) = (i - 1) \times (D(i - 1) + D(i - 2))$

剩下的见代码。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define ll long long
#define pb push_back
#define MP make_pair
#define ull unsigned long long
#define PII pair<int , int>
#define PIL pair<int , long long>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

using namespace std;

const int N = 10001;
const int M = 1000001;
const int HA = 1000000007;
const int INF = 2047483647;
const long long INFL = 9023372036854775807;

ll Pow(ll a , ll b){
    if(b == 0) return 1;
    if(b == 1) return a;
    ll mid = Pow(a , b >> 1);
    if(b % 2 == 0){
        return mid * mid % HA;
    }
    else{
        return (mid * mid % HA) * a % HA;
    }
}

ll fac[M] , inv[M] , d[M];

void prepare(){
    fac[0] = 1;
    rep(i , 1 , M){
        fac[i] = fac[i - 1] * i % HA;   //预处理阶乘
    }
    inv[M] = Pow(fac[M] , HA - 2);
    per(i , M , 1){
        inv[i - 1] = inv[i] * i % HA;   //预处理阶乘逆元
    }
    d[0] = 1 , d[2] = 1;
    rep(i , 3 , M){
        d[i] = (i - 1) * (d[i - 1] + d[i - 2]) % HA;    //预处理错排
    }
}

ll C(int n , int m){    //根据定义求组合数
    if(n < m || n == 0) return 0;
    else if(n == m) return 1;
    else{
        return 1ll * fac[n] % HA * inv[m] % HA * inv[n - m] % HA;   
    }
}

void solve(){
    ll n , m;
    scanf("%lld%lld" , &n , &m);
    if(m > n) puts("0");
    else{
        printf("%lld\n" , C(n , m) * d[n - m] % HA);
    }
}

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    prepare();
    int t; scanf("%d" , &t);
    while(t --) solve();

    return 0;
}