HDU4372 Buildings
@(HDU)[Stirling數, 排列組合]
Problem Description
There are N buildings standing in a straight line in the City, numbered from 1 to N. The heights of all the buildings are distinct and between 1 and N. You can see F buildings when you standing in front of the first building and looking forward, and B buildings when you are behind the last building and looking backward. A building can be seen if the building is higher than any building between you and it.
Now, given N, F, B, your task is to figure out how many ways all the buildings can be.
Input
First line of the input is a single integer T (T<=100000), indicating there are T test cases followed.
Next T lines, each line consists of three integer N, F, B, (0<N, F, B<=2000) described above.
Output
For each case, you should output the number of ways mod 1000000007(1e9+7).
Sample Input
2
3 2 2
3 2 1
Sample Output
2
1
Solution
好吧, 做這題時我是直接看中文翻譯的 ---- 但是, 當我看到這題原文的時候, 我還是不禁要吐槽出題人的英語水平: 題目描述都是什麼鬼 .. 狗屁不通, 表達的意思完全就不對好嗎 ..
言歸正傳, 先 腦補 翻譯 一下題意:
\(n\)个房子在一条线上(\(n \le 2000\)),高度分别为\(1\)~\(n\),现在需要将房子这样放置:从最左往右能看到\(F\)个房子,从最右往左能看到\(B\)个房子,能看到的条件是 两者之间的房子都要低于这个房子.问这样的方案数.
解法也並不算複雜:
因为肯定能看到最高的,,那我们先假定最高的楼房位置确定,那么在其左边还有\(f-1\)个能看见,在其右边还有\(b-1\)个,能看见 .. 所以可以这样将题目转化: 将除最高楼之外的\(n-1\)个楼,分成\(f-1+b-1\) 组,在最高楼左边\(f-1\) 组,在其右边\(b-1\)组,那么分成\(f-1+b-1\) 组 就是第一类Stirling数.\(s[n-1][f-1+b-1]\) .. 将这\(f-1+b-1\) 任意放在最高的楼房的左边和右边, 顺序是确定的, 两边分别的数量也是确定的, 因此组合数为\(C_{f - 1 + b - 1}^{f - 1}\)
故: 答案為$$ans = s[n - 1][f - 1 + b - 1] * c[f - 1 + b - 1][f - 1]$$
Hint: 輸入的數據可能會不合法, 要加以特判
if(f + b - 2 > n)
puts("0");
代碼:
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
inline int read()
{
int x = 0, flag = 1;
char c;
while(! isdigit(c = getchar()))
if(c == '-')
flag *= - 1;
while(isdigit(c))
x = x * 10 + c - '0', c = getchar();
return x * flag;
}
void println(int x)
{
if(x < 0)
putchar('-'), x *= - 1;
if(x == 0)
putchar('0');
int ans[1 << 5], top = 0;
while(x)
ans[top ++] = x % 10, x /= 10;
for(; top; top --)
putchar(ans[top - 1] + '0');
putchar('\n');
}
const int N = 1 << 11;
const int MOD = (int)1e9 + 7;
long long stir[N][N];
int c[N][N];
int main()
{
stir[0][0] = 1;
for(int i = 1; i < N; i ++)
stir[0][i] = (long long)0;
for(long long i = 1; i < N; i ++)
{
stir[i][0] = (long long)0;
for(int j = 1; j <= i; j ++)
stir[i][j] = ((i - 1) * stir[i - 1][j] % MOD + stir[i - 1][j - 1]) % MOD;
}
memset(c, 0, sizeof(c));
c[0][0] = 1;
for(int i = 1; i < N; i ++)
{
c[i][0] = 1;
for(int j = 1; j <= i; j ++)
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
}
int T = read();
while(T --)
{
int n = read(), f = read(), b = read();
if(f + b - 2 >= n)
puts("0");
else
{
int ans = (c[f - 1 + b - 1][f - 1] * stir[n - 1][f - 1 + b - 1]) % MOD;
println(ans);
}
}
}
最新文章
- C++Primer学习笔记(1)
- CentOS下配置nginx conf/koi-win为同一文件的各类错误
- mysql中You can&#39;t specify target table for update in FROM clause错误
- 使用scp将文件/目录拷贝到另一台Linux主机上
- rational rose USE CASE
- mysql:恢复mysql表结构
- MVC中用ajax提交json对象数组
- Oracle 全文索引相关命令
- Heavy Transportation
- Android系统源代码下载
- solr连接数据库
- Struts2 知识体系
- BootstrapTable-加载数据
- 使用HttpClient和WebRequest时POST一个对象的写法
- SQL数据库基础知识
- oracle中not in 和 in 的替代写法
- 实例快速上手UDP和TCP的使用
- C# 在托盘显示图标
- 2014华为机试西安地区A组试题
- Asp.Net 之 <;%%>;相关内联代码块用法