首页 > 代码库 > icpc2016沈阳网络赛1003hannnnah_j’s Biological Test组合数模板题
icpc2016沈阳网络赛1003hannnnah_j’s Biological Test组合数模板题
hannnnah_j’s Biological Test
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Problem Description
hannnnah_j is a teacher in WL High school who teaches biology.
One day, she wants to test m students, thus she arranges n different seats around a round table.
In order to prevent cheating, she thinks that there should be at least k empty seats between every two students.
hannnnah_j is poor at math, and she wants to know the sum of the solutions.So she turns to you for help.Can you help her? The answer maybe large, and you need to mod 1e9+7.
One day, she wants to test m students, thus she arranges n different seats around a round table.
In order to prevent cheating, she thinks that there should be at least k empty seats between every two students.
hannnnah_j is poor at math, and she wants to know the sum of the solutions.So she turns to you for help.Can you help her? The answer maybe large, and you need to mod 1e9+7.
Input
First line is an integer T(T≤1000).
The next T lines were given n, m, k, respectively.
0 < m < n < 1e6, 0 < k < 1000
The next T lines were given n, m, k, respectively.
0 < m < n < 1e6, 0 < k < 1000
Output
For each test case the output is only one integer number ans in a line.
Sample Input
24 2 65 2 1
Sample Output
0 5
思路：
1 #include <iostream> 2 #include <cstdio> 3 4 using namespace std; 5 typedef long long LL; 6 const int p = 1e9 + 7; 7 LL quick_mod(LL a, LL b) { 8 LL ans = 1; 9 a %= p;10 while(b) {11 if(b & 1) {12 ans = ans * a % p;13 b--;14 }15 b >>= 1;16 a = a * a % p;17 }18 return ans;19 }20 21 LL C(LL n, LL m) {22 if(m > n) return 0;23 LL ans = 1;24 for(int i=1; i<=m; i++) {25 LL a = (n + i - m) % p;26 LL b = i % p;27 ans = ans * (a * quick_mod(b, p-2) % p) % p;28 }29 return ans;30 }31 LL Lucas(LL n, LL m) {32 if(m == 0) return 1;33 return C(n % p, m % p) * Lucas(n / p, m / p) % p;34 }35 int main() {36 int k, T, n, m;37 scanf("%d", &T);38 while(T--){39 scanf("%d%d%d", &n, &m, &k);40 if(m == 1) printf("%d\n", n);41 else {42 printf("%d\n", n*Lucas(n-k*m-1, m-1)%p*quick_mod(m, p-2)%p);43 }44 }45 return 0;46 }
看了看别人交的代码，发现自己的好慢
icpc2016沈阳网络赛1003hannnnah_j’s Biological Test组合数模板题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。