FJOI2016 建筑师

昨天考了场省选模拟赛,下来才知道是FJOI2016,不过T1,T2都没在OJ上找到?? T2倒是以前在紫书上面的UVa 1638做到过类似的.

题意概述

给n$n$个建筑,高度为1$1$~n$n$不等,问满足从左往右看有a$a$个建筑,从右往左看有b$b$个建筑的方案数(答案模109+7$10^9+7$,其中多组询问).

数据范围: 10%:1≤n≤10$10/%:1/leq n/leq 10$ 20%:1≤n≤100$20/%:1/leq n/leq 100$ 40%:1≤n≤5∗104,1≤T≤5$40/%:1/leq n/leq 5*10^4,1/leq T /leq5$ 100%:1≤n≤5∗104$100/%:1/leq n/leq 5*10^4$,1≤a,b≤100,1≤T≤2∗105$1/leq a,b/leq 100,1/leq T/leq 2*10^5$.

题目分析:

(为了叙述方便,将建筑视为杆子)

20%$20/%$的解法

20%$20/%$的话和UVa 1638是一样的.

定义状态f(i,j,k)$f(i,j,k)$表示由高度为1$1$~i$i$的i$i$根杆子组成从左看得到j$j$个,从右看得到k$k$个的方案数.

因为对于n$n$个杆子而言,只要相对高度不变,具体高度不影响方案数. 则对于1$1$~i−1$i-1$的i−1$i-1$个杆子而言,它的方案数等同于2 i$2~i$的i−1$i-1$个杆子的方案数.

由于考虑最高的杆子会挡住低的杆子,比较麻烦. 所以从i−1$i-1$转移到i$i$,可以考虑1$1$号杆子的影响.

若放在最左边,左边加1$1$,方案数为f(i−1,j−1,k)$f(i-1,j-1,k)$. 若放在最右边,右边加1$1$,方案数为f(i−1,j,k−1)$f(i-1,j,k-1)$. 而若1$1$号放在中间的话,不会被看见. i−1$i-1$个杆子的话,中间有i−2$i-2$个空隙,方案数为f(i−1,j,k)∗(i−2)$f(i-1,j,k)*(i-2)$.

综上所述,转移方程如下 f(i,j,k)=f(i−1,j−1,k)+f(i−1,j,k−1)+f(i−1,j,k)∗(i−2) $$f(i,j,k)=f(i-1,j-1,k)+f(i-1,j,k-1)+f(i-1,j,k)*(i-2)$$

时间复杂度为O(Tnab)$O(Tnab)$.

40%$40/%$的解法

其实可以发现在上面的方法中左右两边是一样的. 基于此,考虑降维,减少状态.

用f(i,j)$f(i,j)$表示用i个杆子,然后最大的放在最右边,从左能看到j$j$个杆子的方案数. 和上面类似的,可以得到转移方程 f(i,j)=f(i−1,j−1)+f(i−1,j)∗(i−2) $$f(i,j)=f(i-1,j-1)+f(i-1,j)*(i-2)$$

那么最后的答案为 ∑f(i,a)∗f(n−i+1,b)|1≤i≤n $$/sum{f(i,a)*f(n-i+1,b)|1/leq i/leq n}$$

时间复杂度为O(Tn∗max(l,r))$O(Tn*max(l,r))$.

100%$100/%$的解法

话说这个题,我在涨老师的博客上看到了一种特别妙的解法,据说是汪神搞出来的. 先说一下答案(其中su$s_u$表示无符号第一类斯特林数) su(n−1,a+b−2)∗C(a+b−2,a−1) $$s_u(n-1,a+b-2)*C(a+b-2,a-1)$$

下面来解释一下

观察上图,这是从左和从右能看到杆子的一个汇总.

(因为n$n$号杆子无论放在何处均可见,故在下面证明的时候不包含n$n$号杆子.)

以左边为例,一个可见杆子之后跟着一些不可见杆子,如1$1$~2$2$间的杆子是不可见的,且他们都要比1$1$号高度低.将这样一个可见杆子和其后的不可见杆子理解成一个集合,那么像这个样子的集合有a+b−2$a+b-2$个.

对于每一个集合而言,除了最高的杆子(即可见杆子)的位置必须放在最前面以外,其他的杆子其实是可以随意放置的.那么可将其连起来形成一个圆,对于一个圆而言,若从任意一处切开形成的序列中合法序列(即满足最高杆子在最前面)有且仅有一个,即一个圆仅代表一种方案.假设这个集合有k$k$根杆子,那么对于该集合的合法方案就有su(k,1)$s_u(k,1)$种. 那么对于一共的n−1$n-1$根杆子来说,就有su(n−1,a+b−2)$s_u(n-1,a+b-2)$种方案.

这只是保证了有a+b−2$a+b-2$根杆子可见,而对于要使得左边看见a$a$根杆子而言,即在这a+b−2$a+b-2$个集合中任意选择a−1$a-1$个集合放在n$n$号杆子左边,即可.即要满足左边看见a$a$根杆子的方案数为C(a+b−2,a−1)$C(a+b-2,a-1)$.

综上所述,满足条件的方案数为su(n−1,a+b−2)∗C(a+b−2,a−1)$s_u(n-1,a+b-2)*C(a+b-2,a-1)$.

基于此,可以做到O(na+a2)$O(na+a^2)$预处理,O(1)$O(1)$回答询问.

代码实现: