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

-->

示例1

输入

输出

1

2

 #include<cstdio>

 using namespace std;

 typedef long long ll;

 const ll maxn=1e6+;

 const ll mod=1e9+;

 ll v[*maxn];

 void init()

 {

     v[]=;

     for(ll i=;i<*maxn;i++)

         v[i]=v[i-]*i%mod;

 }

 ll exten_gcd(ll a,ll b,ll& x,ll& y)

 {

     ll d=a;

     if(b)

     {

         d=exten_gcd(b,a%b,y,x);

         y-=a/b*x;

     }

     else x=,y=;

     return d;

 }

 ll niyuan(ll a)

 {

     ll x,y;

     ll s=exten_gcd(a,mod,x,y);

     if(s==)return (x%mod+mod)%mod;

     return -;

 }

 ll C(ll n,ll m)

 {

     ll A=v[n];

     ll B=v[m]*v[n-m]%mod;

     return A*niyuan(B)%mod;

 }

 ll suan(ll n,ll m)

 {

     ll t=n+m;

     return (C(t,n)-C(t,n+)+mod)%mod;

 }

 int main()

 {

     init();

     int T;scanf("%d",&T);

     while(T--)

     {

         ll n,m,k;

         scanf("%lld%lld%lld",&n,&m,&k);

         if(m>n||k>m)

         {

             printf("0\n");

             continue;

         }

         ll A,B;

         if(m==k)A=;

         else A=suan(m-,m-k);

         if(n==m)B=;

         else B=suan(n-m+k,n-m);

         printf("%lld\n",A*B%mod);

     }

     return ;

 }

秒客网