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]

BZOJ 2786 Ural1142 Relation 递推

原文：http://blog.csdn.net/popoqqq/article/details/42645283