长沙理工大学第十二届ACM大赛-重现赛 K题

Number of ordered, unlabeled binary rooted trees with n nodes and k leaves

也是The number of Dyck paths of semilength n, having k-1 ddu's [here u = (1,1) and d = (1,-1)].

mod=1000000007


# https://oeis.org/A091894
# https://math.stackexchange.com/questions/2172676/number-of-ordered-unlabeled-binary-rooted-trees-with-n-nodes-and-k-leafs


# binomial取模
def binomial_mod(n, k, mod):
    if k > n:
        return 0
    if k == 0 or k == n:
        return 1
    
    # Initialize numerator and denominator
    num = den = 1
    
    # Compute n! / (k! * (n-k)!) % mod
    for i in range(k):
        num = num * (n - i) % mod
        den = den * (i + 1) % mod
    
    # Compute the modular inverse of denominator
    den_inv = pow(den, mod - 2, mod)
    
    return num * den_inv % mod

# 利用快速幂计算分数取模
def fraction_mod_inverse(a,b,mod):
    # a*(b**(mod-2))%mod
    return pow(b,mod-2,mod)*a%mod

  
# Number of ordered, unlabeled binary rooted trees with n nodes and k leaves 
# 也是The number of Dyck paths of semilength n, having k-1 ddu's [here u = (1,1) and d = (1,-1)].


while True:
    try:
        n,k=map(int,input().split())
        k=k-1
        if  n==0 and k==0:
            ans=1
        elif n==0:
            ans=0
        elif k<=(n)//2:
            numerator=pow(2, (n-2*k-1), mod)*binomial_mod(n-1, 2*k, mod)%mod*binomial_mod(2*k, k, mod)%mod
            denominator=k+1
            ans=fraction_mod_inverse(numerator, denominator, mod)
        else:
            ans=0
        print(ans)
    except:
        break