BZOJ 2786: Ural 1142 Relation - 遞推計算方案數

問題描述

用 '=' 和 '<' 連接 n 個元素，等號連接的視為一個整體（有序集合），求不同連接方案數。

遞推公式推導

設 f[i][j] 表示 i 個元素劃分為 j 個有序集合的方案數。
第 i 個元素：
1. 放入現有 j 個集合之一：f[i-1][j] * j
2. 新建一個集合，插入 j+1 個間隙之一：f[i-1][j-1] * j
故 f[i][j] = j * (f[i-1][j] + f[i-1][j-1])。
答案 ans[n] = Σ f[n][j]。預計算至 n=50。

Python 實現

ans = [0]*60
f = [[0]*60 for _ in range(60)]
ans[1]=1; f[1][1]=1
for i in range(2,51):
    for j in range(1,i+1):
        f[i][j] = f[i-1][j-1]*j + f[i-1][j]*j
        ans[i] += f[i][j]
T = int(input())
for _ in range(T):
    x = int(input())
    print(ans[x])