2018年长沙理工大学第十三届程序设计竞赛 J杯子

63 阅读 0 评论 42 点赞

我是靠谱客的博主安静哈密瓜，最近开发中收集的这篇文章主要介绍2018年长沙理工大学第十三届程序设计竞赛 J杯子，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接：https://www.nowcoder.com/acm/contest/96/J
来源：牛客网

杯子

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

一天durong同学买了一个无限长的杯子，同时买了n个球，并且标号为1，2，3......n，durong同学突然想到一个问题----如果他把n个球依次，也就是按照1，2，3...n的顺序放进杯子里，然后在全部拿出来（注意不一定要等到全部放进去才能拿出球），并且会记录放进和拿出球的顺序，
durong想知道，要满足当第m个球进去后，杯子中此时恰好有k个球，然后仍然要把剩下的n-m个球放进去，最后杯中的球要取光，这样的放进和拿出球的顺序有多少种，答案有可能很大，所以mod上1e9+7

输入描述:

1<=n,m,k<=1e6（m可能大于n，k可能大于m）
第一行一个正整数T，表示数据组数。(1<=T<=10000)
对于每组数据包含一行三个正整数n,m,k。

输出描述:

对于每组数据输出一个正整数表示答案。
由于答案可能过大，所以只需要输出对1e9+7取模后的答案

示例1

输入

2
3 3 3
3 3 2

输出

1
2

 1 #include<cstdio>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll maxn=1e6+5;
 5 const ll mod=1e9+7;
 6 ll v[2*maxn];
 7 void init()
 8 {
 9     v[0]=1;
10     for(ll i=1;i<2*maxn;i++)
11         v[i]=v[i-1]*i%mod;
12 }
13 ll exten_gcd(ll a,ll b,ll& x,ll& y)
14 {
15     ll d=a;
16     if(b)
17     {
18         d=exten_gcd(b,a%b,y,x);
19         y-=a/b*x;
20     }
21     else x=1,y=0;
22     return d;
23 }
24 ll niyuan(ll a)
25 {
26     ll x,y;
27     ll s=exten_gcd(a,mod,x,y);
28     if(s==1)return (x%mod+mod)%mod;
29     return -1;
30 }
31 ll C(ll n,ll m)
32 {
33     ll A=v[n];
34     ll B=v[m]*v[n-m]%mod;
35     return A*niyuan(B)%mod;
36 }
37 ll suan(ll n,ll m)
38 {
39     ll t=n+m;
40     return (C(t,n)-C(t,n+1)+mod)%mod;
41 }
42 int main()
43 {
44     init();
45     int T;scanf("%d",&T);
46     while(T--)
47     {
48         ll n,m,k;
49         scanf("%lld%lld%lld",&n,&m,&k);
50         if(m>n||k>m)
51         {
52             printf("0n");
53             continue;
54         }
55         ll A,B;
56         if(m==k)A=1;
57         else A=suan(m-1,m-k);
58         if(n==m)B=1;
59         else B=suan(n-m+k,n-m);
60         printf("%lldn",A*B%mod);
61     }
62     return 0;
63 }