2018年长沙理工大学程序设计竞赛 J - 杯子

题意： 链接：https://www.nowcoder.com/acm/contest/96/J
一天durong同学买了一个无限长的杯子，同时买了n个球，并且标号为1，2，3......n，durong同学突然想到一个问题----如果他把n个球依次，

也就是按照1，2，3...n的顺序放进杯子里，然后在全部拿出来（注意不一定要等到全部放进去才能拿出球），并且会记录放进和拿出球的顺序，
durong想知道，要满足当第m个球进去后，杯子中此时恰好有k个球，然后仍然要把剩下的n-m个球放进去，最后杯中的球要取光，

这样的放进和拿出球的顺序有多少种，答案有可能很大，所以mod上1e9+7。

 

kuangbing的博客

这个题解讲的挺好的

 

对于n个0，m个1 的任意前缀0的个数不小于1的种数是 C(n+m,n)-C(n+m,m-1)。

卡特兰数是n = m 的特殊情况， 通项公式为 C(2 * n, n) / (n + 1)

 

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int,int>
using namespace std;

const int N=2e6+7;
const int M=1e4+7;
const int inf=0x3f3f3f3f;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9 + 7;

int n, m, k;
LL f[N], inv[N];

LL fastPow(LL a, LL b) {
    LL ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod; b >>= 1;
    }
    return ans;
}
void init() {
    f[0] = 1;
    for(int i = 1; i < N; i++) {
        f[i] = f[i - 1] * i % mod;
    }
    for(int i = N - 1; i >= 0; i--)
        inv[i] = fastPow(f[i], mod - 2);

}

LL C(int n, int m) {
    if(n < m) return 0;
    return f[n] * inv[m] % mod * inv[n - m] % mod;
}

LL getCatalan(int n, int m) {
   return (C(n + m, n) - C(n + m, m - 1) + mod) % mod;
}

int main() {
    init();
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d", &n, &m, &k);
        if(m > n || k > m) {
            puts("0");
            continue;
        }
        LL ret1 = getCatalan(m - 1, m - k);
        LL ret2 = getCatalan(n - (m - k), n - m);
        printf("%lldn", ret1 * ret2 % mod);
    }
    return 0;
}
/*
*/