题目描述
求有多少种 1 到 n 的排列 a，满足序列恰好有 m 个位置 i，使得 ai=i。
答案对 109+7 取模。
输入格式
本题单测试点内有多组数据。
输入的第一行是一个整数 T，代表测试数据的组数。
以下 T 行，每行描述一组测试数据。
对于每组测试数据，每行输入两个整数，依次代表 n 和 m。
输出格式
共输出 T 行，对于每组测试数据，输出一行一个整数代表答案。
输入输出样例
输入 #1复制
5 1 0 1 1 5 2 100 50 10000 5000
输出 #1复制
0 1 20 578028887 60695423
说明/提示
数据规模与约定
本题共 20 个测试点，各测试点等分，其数据规模如下表。
| 测试点编号 | T= | n,m≤ | 测试点编号 | T= | n,m≤ |
|---|---|---|---|---|---|
| 1∼3 | 103 | 8 | 10∼12 | 103 | 103 |
| 4∼6 | 103 | 12 | 13∼14 | 5×105 | 103 |
| 7∼9 | 103 | 100 | 15∼20 | 5×105 | 106 |
对于全部的测试点，保证 1≤T≤5×105，1≤n≤106，0≤m≤106。
代码实现：
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define ll long long using namespace std; const int N=1010101; const ll mod=1e9+7; ll t, n, m, inv[N], fac[N], pt[N], res; ll qpow(ll x, ll y) { res = 1; while(y > 0) { if(y % 2) res = (res * (x % mod)) % mod; x = ((x % mod) * (x % mod)) % mod; y >>= 1; } return res; } int main() { inv[0] = 1; inv[1] = 1; pt[0] = 1; pt[2] = 1; pt[3] = 2; fac[1] = 1; for(int i=2; i<=N; ++i) fac[i] = ((fac[i-1] % mod) * (i % mod)) % mod; for(int i=4; i<=N; ++i) if(i%2 == 0) pt[i] = ((pt[i-1] % mod * i % mod) % mod + 1) % mod; else pt[i] = ((pt[i-1] % mod * i % mod) % mod - 1 + mod) % mod; inv[N] = qpow(fac[N], mod-2); for(ll i=N; i>=2; --i) inv[i-1] = ((inv[i] % mod) * i) % mod; scanf("%lld", &t); while(t--) { scanf("%lld%lld", &n, &m); printf("%lld\n", (((fac[n] % mod * inv[n-m] % mod) % mod * inv[m] % mod) % mod * pt[n-m] % mod) % mod); } return 0; }
)
