[BZOJ4517] [Sdoi2016] 排列计数 (数学)

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

5
1 0
1 1
5 2
100 50
10000 5000

Sample Output

0
1
20
578028887
60695423

HINT

Source

　　鸣谢Menci上传

Solution

　　我们选$m$个数稳定，其余$n - m$个数不稳定，那么方案数即为错位全排列

　　选$m$个数的方案有$C_{n}^{m}$种，乘起来即可。

　　排列数计算除法用乘法逆元替代，好像用exgcd常数小一些= =

　　错排公式：$f[n] = (n - 1)(f[n - 1] + f[n - 2]) = nf[n - 1] + (-1)^{n}$

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const ll MOD = ;

 ll a[], f[], inv[];

 ll pow(ll x)

 {

     ll ans = , y = MOD - ;

     for(; y; y >>= , x = x * x % MOD)

         if(y & ) ans = ans * x % MOD;

     return ans;

 }

 ll C(int x, int y)

 {

     return f[x] * inv[x - y] % MOD * inv[y] % MOD;

 }

 int main()

 {

     int t, n, m;

     f[] = , a[] = , a[] = ;

     for(int i = ; i <= ; i++)

         f[i] = f[i - ] * i % MOD;

     for(int i = ; i <= ; i++)

         inv[i] = pow(f[i]);

     for(int i = ; i <= ; i++)

         a[i] = (a[i - ] + a[i - ]) * (i - ) % MOD;

     scanf("%d", &t);

     while(t--)

     {

         scanf("%d%d", &n, &m);

         if(m <= n) printf("%lld\n", C(n, m) * a[n - m] % MOD);

         else puts("");

     }

     return ;

 }

秒客网