[SDOI2016]排列计数
题目描述
求有多少种 \(1\) 到 \(n\) 的排列 \(a\)，满足序列恰好有 \(m\) 个位置 \(i\)，使得 \(a_i = i\)。
答案对 \(10^9 + 7\) 取模。
输入格式
本题单测试点内有多组数据。
输入的第一行是一个整数 \(T\)，代表测试数据的整数。
以下 \(T\) 行，每行描述一组测试数据。
对于每组测试数据，每行输入两个整数，依次代表 \(n\) 和 \(m\)。
输出格式
共输出 \(T\) 行，对于每组测试数据，输出一行一个整数代表答案。
样例 #1
样例输入 #1
5
1 0
1 1
5 2
100 50
10000 5000
样例输出 #1
0
1
20
578028887
60695423
提示
数据规模与约定
本题共 20 个测试点，各测试点等分，其数据规模如下表。
| 测试点编号 | \(T =\) | \(n, m \leq\) | 测试点编号 | \(T =\) | \(n, m \leq\) |
|---|---|---|---|---|---|
| \(1\sim 3\) | \(10^3\) | \(8\) | \(10 \sim 12\) | \(10^3\) | \(10^3\) |
| \(4 \sim 6\) | \(10^3\) | \(12\) | \(13 \sim 14\) | \(5 \times 10^5\) | \(10^3\) |
| \(7 \sim 9\) | \(10^3\) | \(100\) | \(15 \sim 20\) | \(5 \times 10^5\) | \(10^6\) |
| 对于全部的测试点，保证 \(1 \leq T \leq 5 \times 10^5\)，\(1 \leq n \leq 10^6\)，\(0 \leq m \leq 10^6\)。 |
问题是要求有 \(m\) 个稳定的位置,我们可以转换成求 \(n-m\) 个不稳定的位置
则从 \(n\) 个数中找 \(n-m\) 个位置的式子是 \(C^{n - m}_n\)
而根据错排式子：若有 \(n\) 个位置，则 \(f(n) = (n - 1) * (f(n - 1) + f(n - 2))\)
则可以得到最终式子 \(c^{n-m}_n * f(n - m)\)
其中 \(c^{n-m}_n\) 和 \(f(n - m)\) 可以预处理得到
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const long long mod = 1e9 + 7;
long long dp[5211314], n, m, t;
long long inv[5211314], f[5211314];
int main() {
dp[0] = 1;
//注意dp[0]为1
dp[1] = 0;
dp[2] = 1;
f[0] = f[1] = inv[0] = inv[1] = 1;
for (int i = 1; i <= 1000000; ++ i) {
if (i != 1 && i != 2) dp[i] *= (i - 1);
dp[i] %= mod;
dp[i + 1] += dp[i];
dp[i + 1] %= mod;
dp[i + 2] += dp[i];
dp[i + 2] %= mod;
if (i >= 2) {
f[i] = f[i - 1] * i % mod;
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
}
for (int i = 2; i <= 1000000; ++ i) {
inv[i] = inv[i - 1] * inv[i] % mod;
}
scanf("%lld", &t);
while (t --) {
scanf("%lld%lld", &n, &m);
printf("%lld\n", (((f[n] * inv[n - m] % mod) * inv[m] % mod) * dp[n - m] % mod));
}
return 0;
}