题解 | 信息学奥赛一本通 树屋阶梯

思路

很明显所有的阶梯都顶到某一列的顶部.
枚举顶到第一列阶梯顶部的阶梯的长度,接下来列都不能到第一列,前列的最下面行全部空出来,这样子就形成一个子问题,而最后列也是一个子问题,中间空出来那部分也由该子问题扩充过去.

如图,第一列选了黄色部分的三块,红色部分是一个子问题,绿色部分是一个子问题,中间白色部分由绿色部分扩充过来.
设是行列的答案,可以枚举第一列选的长度.这就是卡特兰数的递推式,求卡特兰数即可.此题需要高精度.所以用Python/Java.

代码

N = int(input())
NN = N<< 1
vis = [0 for i in range(NN + 5)]
p = [0 for i in range(NN + 5)]
h = [0 for i in range(NN + 5)]
cnt = [0 for i in range(NN + 5)]
tot = 0
for i in range( 2, NN + 1 ):
    if vis[i] == 0:
        tot += 1
        p[tot] = i
        h[i] = i
    for j in range( 1, tot + 1 ):
        if i * p[j] > NN :
             break 
        vis[i * p[j]] = 1
        h[i * p[j]] = p[j]
        if i % p[j] == 0:
            break;
for i in range( 2, N + 1 ):
    cnt[i + N] += 1
    cnt[i] -= 1
ans = 1
for tmp in range( 1, NN ):
    i = NN + 1 - tmp
    if vis[i] == 0:
        ans = ans * ( i ** cnt[i] )
    else:
        cnt[h[i]] += cnt[i]
        cnt[i // h[i]] += cnt[i]
print(ans);