程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> BZOJ 2786 Ural1142 Relation 遞推

BZOJ 2786 Ural1142 Relation 遞推

編輯:關於C++

題目大意:用'='和'<'連接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]


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved