[Bzoj4517]排列技术（错排 + 预处理）

4517: [Sdoi2016]排列计数

---

Time Limit: 60 Sec  Memory Limit: 128 MB
Submit: 1508  Solved: 915
[Submit][Status][Discuss]

Description

---

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

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

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

满足条件的序列可能很多，序列数对 10^9+7 取模。

Input

---

第一行一个数 T，表示有 T 组数据。

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

T=500000，n≤1000000，m≤1000000

 

Output

---

输出 T 行，每行一个数，表示求出的序列数

 

Sample Input

---

Sample Output

---

分析：

---

可以分成两部分：

 

一部分是从n个数里选m个数稳定的，方案数是C(n,m) = n！ / m ！（n - m）！----①

 

剩下一部分就是n - m个数，要使这些数不能放在吧本身位置上的方案数，和①相乘就好了。

 

很显然是错排公式。。错排递推式f（i） = （i - 1） * （f（i - 1） + f（i - 2））---②

 

① * ②为答案，都可以O(n)预处理，求逆元，求阶乘，求f函数

 

然后最后O（1）回答就好了。。

 

AC代码：

---

# include <cstdio>

using namespace std;

const int N = ;

const long long P = 1e9 + ;

long long inv[N],f[N],fac_inv[N],fac[N];

void work(){

    inv[] = inv[] = 1LL;

    fac_inv[] = fac_inv[] = 1LL;

    fac[] = fac[] = 1LL;

    f[] = 1LL;f[] = 1LL;

    for(long long i = ;i <= 1e6;i++){

        inv[i] = (P - (P / i)) * inv[P % i] % P;

        fac_inv[i] = fac_inv[i - ] * inv[i] % P;

        fac[i] = i * fac[i - ] % P;

    }

}

int T;

long long a,b,c;

int main(){

    scanf("%d",&T);

    work();

    while(T--){

    scanf("%lld %lld",&a,&b);

    c = fac_inv[b] * fac_inv[a - b] % P;

    printf("%lld\n",(fac[a] * c) % P * f[a - b] % P);

   }

}