程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4372 Count the Buildings（組合數學，第一類Stirling數）

HDU 4372 Count the Buildings（組合數學，第一類Stirling數）

編輯：C++入門知識

HDU 4372 Count the Buildings（組合數學，第一類Stirling數）

HDU 4372

題意：有n個建築高度為1~n，從前看能看到f個，從後看能看到b個，求可能有多少種排序情況。

思路：

五個小時花了3.5小時在上面，結果靠強行yy出了遞推式（事後發現。。yy對了95%，跪在各種細節上，比賽結束也沒A掉。。

只能說大力出奇跡！但這種奇跡往往會毀在不經意的細節上orz

分析幾組數據我們可以發現，最高的n號樓一定是可以看到的，無論是從左還是右。

那麼民那桑，先固定住n號樓的位置，將n號樓左邊分為f-1組，右邊b-1組，且用每組最高的那個元素代表這一組；

而後我們可以發現樓n的左邊，從左到右，組與組之間最高的元素一定是單調遞增的！

且每組中的最高元素一定排在該組的最左邊，每組中的其它元素可以任意排列（相當於這個組中所有元素的環排列，所謂環排列就是一個元素位置固定其他元素自己動，方案數等於(n-1)!）。

右邊同理。

例如：n = 5 , b = 3 , f = 2。

顯然n號樓所在位置一定在第3，或第4：XX5XX或XXX5X

當位置在3之時,左邊2個元素分成2組，顯然符合結論；

當位置在4之時,左邊3個元素分成2組，左邊可能的情況為：1 32 5X，21 3 5X ，2 31 5X ， 1 42 5X ，21 4 5X ，2 41 5X ，1 43 5X ，31 4 5X ，3 41 5X...

均滿足結論（當然這裡的X很明顯已經求出來了XP

故我們可以先把n-1個元素分成f-1+b-1組,每組做環排列，累計方案數即是答案。

而 $n$ 個人分成 $k$ 組做環排列的方法數目，我們稱之為第一類stirling數

答案：ans(n, f, b) = C[f + b - 2][f - 1] * S[n - 1][f + b - 2];

code：

/*
* @author Novicer
* language : C++/C
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 2147483647
#define cls(x) memset(x,0,sizeof(x))
#define rise(i,a,b) for(int i = a ; i <= b ; i++)
using namespace std;
const double eps(1e-8);
typedef long long lint;

const int maxn = 2000 + 5;
const lint mod = 1e9 + 7;
lint S[maxn][maxn];
lint C[maxn][maxn];

void init(){  
    for(int i = 0 ; i < maxn ; i++){  
        C[i][0]=1;  
        C[i][i]=1;  
        S[i][0]=0;  
        S[i][i]=1;  
        for(int j = 1 ; j < i ; j++){  
            C[i][j]=(C[i-1][j]%mod+C[i-1][j-1]%mod)%mod;  
            S[i][j]=((i-1)%mod*S[i-1][j]%mod+S[i-1][j-1]%mod);  
        }  
    }  
}  
int main(){
//	freopen(input.txt,r,stdin);
	int t ; cin >> t;
	init();
	while(t--)	{
		lint n,f,b;
		scanf(%I64d%I64d%I64d,&n,&f,&b);  
		lint ans;
		if(b+f-2 <= 2000)
	        ans=C[f+b-2][f-1]%mod*S[n-1][f+b-2]%mod;  
		else
			ans = 0 % mod;
        printf(%I64d
,ans);
	}
	return 0;
}