洛谷 P1641 [SCOI2010]生成字符串

题目描述
lxhgww最近接到了一个生成字符串的任务，任务需要他把n个1和m个0组成字符串，但是任务还要求在组成的字符串中，在任意的前k个字符中，1的个数不能少于0的个数。现在lxhgww想要知道满足要求的字符串共有多少个，聪明的程序员们，你们能帮助他吗？

输入格式
输入数据是一行，包括2个数字n和m

输出格式
输出数据是一行，包括1个数字，表示满足要求的字符串数目，这个数可能会很大，只需输出这个数除以20100403的余数
题解：比较经典的卡特兰数，关于卡特兰数，我明天可能会补上讲解与练习（咕咕咕警告

#include <stdio.h>
#define int long long 
#define modd 20100403
int n,m,i; 
int nn,mm,ny;
long long qkpow(long long a,long long p,long long mod){
    long long t=1,tt=a%mod;
    while(p){
        if(p&1)t=t*tt%mod;
        tt=tt*tt%mod;
        p>>=1;
    }
    return t;
}
int getni(long long a,long long mod){
    return qkpow(a,mod-2,mod);
}
main(){
    scanf("%lld%lld",&n,&m);
    nn=n-m+1;mm=n+1;
    for(i=mm;i<=n+m;i++)
       nn=(nn*i)%modd;
    for(i=1;i<=m;i++)
       mm=(mm*i)%modd;
    ny=getni(mm,modd);
    int ans;
    ans=ny*nn%modd;
    ans=ans+modd;
    ans=ans%modd;
    printf("%lld",ans);
    return 0; 
}

洛谷 P1641 [SCOI2010]生成字符串

原文：https://www.cnblogs.com/southking/p/12339773.html