首页 > 代码库 > 【BZOJ4517】【SDOI2016】排列计数 [数论]
【BZOJ4517】【SDOI2016】排列计数 [数论]
4517: [Sdoi2016]排列计数
Time Limit: 60 Sec Memory Limit: 128 MBSubmit: 1206 Solved: 732
[Submit][Status][Discuss]
Description
求有多少种长度为 n 的序列 A，满足以下条件：
1 ~ n 这 n 个数在序列中各出现了一次
若第 i 个数 A[i] 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的
满足条件的序列可能很多，序列数对 10^9+7 取模。
Input
第一行一个数 T，表示有 T 组数据。
接下来 T 行，每行两个整数 n、m。
Output
输出 T 行，每行一个数，表示求出的序列数
Sample Input
5
1 0
1 1
5 2
100 50
10000 5000
1 0
1 1
5 2
100 50
10000 5000
Sample Output
0
1
20
578028887
60695423
1
20
578028887
60695423
HINT
T=500000，n≤1000000，m≤1000000
Main idea
求所有排列中恰好有m个 a[i]=i 的个数。
Solution
直接运用组合数和错排公式上一波即可。
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 #include<map> 9 using namespace std; 10 typedef long long s64;11 12 const int ONE = 1000005;13 const int MOD = 1e9+7;14 15 int T,n,m;16 int fac[ONE], inv[ONE], D[ONE];17 18 int get()19 { 20 int res=1,Q=1;char c; 21 while( (c=getchar())<48 || c>57 ) 22 if(c==‘-‘)Q=-1; 23 res=c-48; 24 while( (c=getchar())>=48 && c<=57 ) 25 res=res*10+c-48; 26 return res*Q;27 }28 29 int Quickpow(int a, int b)30 {31 int res = 1;32 while(b)33 {34 if(b & 1) res = (s64)res * a % MOD;35 a = (s64)a * a % MOD;36 b >>= 1;37 }38 return res;39 }40 41 void Deal_first()42 {43 int Limit = ONE-3;44 45 fac[1] = 1;46 for(int i=2; i<=Limit; i++)47 fac[i] = (s64)fac[i-1] * i % MOD; 48 49 inv[Limit] = Quickpow(fac[Limit], MOD-2);50 for(int i=Limit-1; i>=0; i--)51 inv[i] = (s64)inv[i+1] * (i+1) % MOD;52 53 D[0] = D[2] = 1;54 for(int i=3; i<=Limit; i++)55 D[i] = (s64)(i-1) * (D[i-1] + D[i-2]) % MOD;56 }57 58 int C(int n,int m)59 {60 if(n == m) return 1;61 return (s64)fac[n] * inv[m] % MOD * inv[n-m] % MOD;62 }63 64 int Query(int n,int m)65 {66 return (s64)C(n,m) * D[n-m] % MOD;67 }68 69 int main()70 {71 Deal_first();72 T = get();73 while(T--)74 {75 n = get(); m = get();76 printf("%d\n", Query(n,m));77 }78 }
【BZOJ4517】【SDOI2016】排列计数 [数论]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。