4517: [Sdoi2016]排列计数
Time Limit: 60 Sec Memory Limit: 128 MB
Submit: 1508 Solved: 915
[Submit][Status][Discuss]
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
Sample Output
分析：
可以分成两部分：
一部分是从n个数里选m个数稳定的，方案数是C(n,m) = n！ / m ！（n - m）！----①
剩下一部分就是n - m个数，要使这些数不能放在吧本身位置上的方案数，和①相乘就好了。
很显然是错排公式。。错排递推式f（i） = （i - 1） * （f（i - 1） + f（i - 2））---②
① * ②为答案，都可以O(n)预处理，求逆元，求阶乘，求f函数
然后最后O（1）回答就好了。。
AC代码：
# include <cstdio>
using namespace std;
const int N = ;
const long long P = 1e9 + ;
long long inv[N],f[N],fac_inv[N],fac[N];
void work(){
inv[] = inv[] = 1LL;
fac_inv[] = fac_inv[] = 1LL;
fac[] = fac[] = 1LL;
f[] = 1LL;f[] = 1LL;
for(long long i = ;i <= 1e6;i++){
inv[i] = (P - (P / i)) * inv[P % i] % P;
fac_inv[i] = fac_inv[i - ] * inv[i] % P;
fac[i] = i * fac[i - ] % P;
} }
int T;
long long a,b,c;
int main(){
scanf("%d",&T);
work();
while(T--){
scanf("%lld %lld",&a,&b);
c = fac_inv[b] * fac_inv[a - b] % P;
printf("%lld\n",(fac[a] * c) % P * f[a - b] % P);
}
}