题目描述
求有多少种长度为n的系列A,满足以下条件:
1~n这n个数在序列中各出现一次;若第i个数a[i]的值为i,则称i是稳定的。序列恰有m个数是稳定的。
输出序列个数对1e9+7取模的结果。
Solution
显然是从N个数中选m个数稳定,剩下的错排。答案即为:\(C^m_n * d[n - m]\)
\(C^m_n = \frac{n!}{m!(n - m)!} = n! * (m!)^{p - 2} * ((n - m)!)^{p - 2},p = 1e9 +7\)
\(d[n] = (n - 1) (d[n - 1] + d[n - 2])\)
#include <iostream>
#include <cstdio>
using namespace std;
inline long long read() {
long long x = 0; int f = 0; char c = getchar();
while (c < '0' || c > '9') f |= c == '-', c = getchar();
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f? -x : x;
}
const int mod = 1e9 + 7;
const int maxn = 1000006;
int T, n, m;
long long d[maxn], c[maxn];
inline long long pow(long long a, long long k) {//快速幂
long long x = 1;
while (k) {
if (k & 1) x = x * a % mod;
a = a * a % mod; k >>= 1;
}
return x;
}
int main() {
T = read();
c[0] = 1;//预处理
for (int i = 1; i <= maxn; ++i) c[i] = c[i - 1] * i % mod;
d[1] = 0; d[0] = 1;
for (int i = 2; i <= maxn; ++i)
d[i] = (d[i - 1] + d[i - 2]) % mod * (i - 1) % mod;
while (T--) {
n = read(); m = read();
printf("%lld\n",d[n - m] % mod *
c[n] * pow(c[m], mod - 2) % mod * pow(c[n - m], mod - 2) % mod);
}
return 0;
}