[abc] AtCoder Beginner Contest 205

前言

传送门 :

E. White and Black Balls

t a g : tag : tag:基础课原题 组合记数 画图分析 卡特兰数 题意 : 给定 n n n个白球, m m m个黑球,询问有多少种合法放置

条件 ： 对于所有的 i i i满足 c n t w i < = c n t b i + K cnt_{wi}(n,m)的路径数 (0,0)−>(n,m)的路径数 也就是从 ( 0 , 0 ) − > ( n + k + 1 , m − k − 1 ) (0,0) ->(n+k+1,m-k-1) (0,0)−>(n+k+1,m−k−1)的路径数

即答案就是 C n + m n − C n + m m − k − 1 C_{n+m}^n -C_{n+m}^{m-k-1} Cn+mn​−Cn+mm−k−1​

Code

int fact[N],infact[N];

int qmi(int a,int b){
    int res = 1;
    while(b){
        if(b&1) res = (ll)res*a%mod;
        a = (ll) a*a%mod;
        b>>=1;
    }
    return res;
}

void init() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i >n>>m>>k;
    
    if(n > k + m){
    	cout