Cow Pedigrees

nocows

Python

def run(nodes,height):
    # This stores the number of ways to make a tree. ways[x][y] gives the number
    # of ways to make a tree of x nodes and y height
    ways = [[0 for _ in range(height+1)] for _ in range(nodes+1)]
    ways[1][1] = 1 # There is one way to make a tree of one node and height 1

    # This also stores the number of ways to make a tree - allways[x][y] gives
    # the number of ways to make a tree of x nodes and up to y height
    allways = [[0]*(height+1) for _ in range(nodes+1)]
    #allways[1][1] = 1

    # A tree can be made by combining two smaller trees with one other node.
    for h in range(2,height+1):
        for n in range(1,nodes+1,2): # We only care about trees with odd number of nodes
            l = 1
            while l <= n-l-1: # How many nodes in the left subtree
                if l == n-l-1: d = 1
                else: d = 2
                ways[n][h] += d*(ways[l][h-1]*allways[n-l-1][h-2] \
                                +allways[l][h-2]*ways[n-l-1][h-1] \
                                +ways[n-l-1][h-1]*ways[l][h-1])
                ways[n][h] %= 9901
                l += 2
        for i in range(nodes):
            allways[i][h-1] += ways[i][h-1]+allways[i][h-2]
            allways[i][h-1] %= 9901
    print(ways[nodes][height])
    return ways[nodes][height]

def main():
    with open('nocows.in','r') as fIn:
        nodes, height = map(int,fIn.read().split())
    with open('nocows.out','w') as fOut:
        fOut.write(str(run(nodes,height))+'\n')

if __name__ == '__main__':
    main()