首页 > 代码库 > 2016 ACM/ICPC Asia Regional Shenyang Online 1003/HDU 5894 数学/组合数/逆元

2016 ACM/ICPC Asia Regional Shenyang Online 1003/HDU 5894 数学/组合数/逆元

2024-08-14 05:58:15   220人阅读

hannnnah_j’s Biological Test

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 802    Accepted Submission(s): 269


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.
 

 

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
 

 

Output
For each test case the output is only one integer number ans in a line.
 

 

Sample Input
2
4 2 6
5 2 1
 

 

Sample Output
05
 

 

Source
2016 ACM/ICPC Asia Regional Shenyang Online
 
题意：一个大小为 nn 的环，选 mm 个位置涂黑，要求相邻两个黑点之间至少间隔 kk 个白点，问方案数。
题解：n-m个座位分成m份，每份不小于k，也就是剩余n-m-m*k个相同的球放到m个不同的盒子里公式为C(n-m*k-m, m);
nn个相同的球放到mm个不同的盒子里公式是C(nn+mm-1, mm-1);
所以代入nn=n-m-m*k , mm=m;
C(n - m -m*k + m -1 , m-1) = C(n - m*k -1，m - 1)

ans = n * C(n - m*k -1，m - 1)/m；

乘n相当于第一个人有n种选择，而学生在这里都是一样的，所以要是重复计算了m次，最后除以m。

逆元 费马小处理

 1 /****************************** 2 code by drizzle 3 blog: www.cnblogs.com/hsd-/ 4 ^ ^    ^ ^ 5  O      O 6 ******************************/ 7 #include<bits/stdc++.h> 8 #include<iostream> 9 #include<cstring>10 #include<cmath>11 #include<cstdio>12 #define ll long long13 #define mod 100000000714 #define PI acos(-1.0)15 #define N 100000000016 using namespace std;17 ll quickmod(ll a,ll b)18 {19     ll sum=1;20     while(b)21     {22         if(b&1)23             sum=(sum*a)%mod;24         b>>=1;25         a=(a*a)%mod;26     }27     return sum;28 }29 ll combine1(ll n,ll m) //计算组合数C(n,m)30 {31     if(n<0||m<0)32         return 0;33     ll sum=1; //线性计算34     for(ll i=1,j=n;i<=m;i++,j--)35         sum=(((sum*j)%mod)*quickmod(i,mod-2))%mod;36     return sum;37 }38 int t;39 ll nn,mm,kk;40 int main()41 {42     while(scanf("%d",&t)!=EOF)43     {44         for(int i=1;i<=t;i++)45         {46             scanf("%I64d %I64d %I64d",&nn,&mm,&kk);47             if(mm==1)48                 printf("%I64d\n",nn);49             else50                printf("%I64d\n",(((combine1(nn-mm*kk-1,mm-1)%mod)*quickmod(mm,mod-2))%mod*nn)%mod);51         }52     }53     return 0;54 }

 

 

2016 ACM/ICPC Asia Regional Shenyang Online 1003/HDU 5894 数学/组合数/逆元


联系
我们