《P4071 [SDOI2016] 排列计数》

题目描述

求有多少种 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 个测试点，各测试点等分，其数据规模如下表。

对于全部的测试点，保证 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; }