BZOJ 2786 Ural1142 Relation 遞推

BZOJ 2786 Ural1142 Relation 遞推

題目大意：用'='和'<'連接n個元素，等號之間看做一個整體，求方案數

令f[i][j]表示i個數劃分成j個有序集合的方案數

如果將第i個數劃分進原有的集合中，方案數為f[i-1][j]*j

如果將第i個數新建一個集合插進某個位置，方案數為f[i-1][j-1]*j

故f[i][j]=f[i-1][j-1]*j+f[i-1][j]*j

ans = [0] * 60
f = [ ([0] * 60) for i 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(raw_input())
for i in range(1,T+1):
	x=int(raw_input())
	print ans[x]