HDU4372 Count the Buildings

題目描述

Solution

思路很妙。
考慮從最高的一個(gè)樓房將序列分開，左邊可以看到$F$個(gè)，右邊可以看到$B$個(gè)，一個(gè)樓房可以被看到，則一定是其之前沒(méi)有比它高的樓房，其之后有若干個(gè)比它矮的樓房，考慮將這樣的一個(gè)高樓房+若干個(gè)矮樓房看做一個(gè)組，除去最高的樓房，相當(dāng)于左邊有$F?1$組，右邊有$B?1$組，一共$F?B?2$組，總方案數(shù)相當(dāng)于把樓房放進(jìn)每個(gè)組方案數(shù)乘上組之間排列的方案數(shù)。

顯然組與組之間排列，方案數(shù)為$C(f+b?2,b?1)$，而分組的方案數(shù)是$n?1$個(gè)數(shù)放入$f+b?2$個(gè)圓排列的方案數(shù)。

時(shí)間復(fù)雜度$O(N^2+Q)$。

Code

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <string.h> //#include <unordered_set> //#include <unordered_map> //#include <bits/stdc++.h>#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondusing namespace std;template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; } template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI;const lod eps=1e-11; const lod pi=acos(-1); const int oo=1<<30; const ll loo=1ll<<62; const int mods=1e9+7; const int MAXN=2005; const int INF=0x3f3f3f3f;//1061109567 /*--------------------------------------------------------------------*/ inline int read() {int f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }return x*f; } int s[MAXN][MAXN],c[MAXN][MAXN]; void init() {for (int i=0;i<MAXN;i++) c[i][0]=c[i][i]=1;for (int i=0;i<MAXN;i++) s[i][i]=1;for (int i=1;i<MAXN;i++)for (int j=1;j<i;j++){c[i][j]=(c[i-1][j-1]+c[i-1][j])%mods;s[i][j]=(1ll*(i-1)*s[i-1][j]+s[i-1][j-1])%mods;}return; } int main() {init();int Case=read();while (Case--){int n=read(),f=read(),b=read(),ans=1ll*s[n-1][f+b-2]*c[f+b-2][f-1]%mods;printf("%d\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的HDU4372 Count the Buildings的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。