题目
点这里看题目。
分析
懂了懂了，数数题都是毒瘤。
考虑我们可以怎么去震柱子。显然我们可以从高往低去震，但是这样分析无法导出一个解法。
另一个方式就是从后往前去震；这样我们可以导出一个结论：
如果当前柱子之后有高度为 (1sim h) 的柱子各一根，那么当前柱子及之前的柱子，如果高度 (le h) ，都会被直接震没。
因此我们可以将最大的 (h) 看作 " 高度阈值 " ，把那 (1sim h) 的 (h) 个柱子称为 " 标准柱 " 。
考虑一个 DP ：
(f_{i,j}) 表示后 (i) 个柱子，此时高度阈值为 (j) 时的方案数。
为了便于转移，设两个参数 (c_0) 为后 (i-1) 个柱子中钦定消失的数量， (c_1) 为钦定存在的数量。
此外，我们需要区分一下同样高度的两个柱子（比如染色）以便转移，最终答案就需要除掉 (2^n) 。
分类讨论一下转移：
-
如果 (i) 钦定消失，那么阈值不变，从 (f_{i-1,j}) 转移。
此时有 (2j) 个可用高度，其中有 (j) 个分配给了标准柱，还有 (c_0) 个已经分配，所以系数为 (j-c_0) 。
-
如果 (i) 钦定保留，我们同样考虑它的高度：
-
如果 (i) 的高度 (> j+1) ，我们就稍后考虑它的真实高度，此时从 (f_{i-1,j}) 转移，系数为 1 。
-
如果 (i) 的高度为 (j+1) ，由于有些标准柱的高度还未确定，所以我们需要考虑接起来之后的高度阈值。
枚举一个新阈值 (k) ，此时是从 (f_{i-1,j}) 转移到 (f_{i,k}) 。
计算系数，有如下几个部分：
- 选定标准柱的位置 (inom{c_1-j}{k-j-1}) 。
- 确定当前柱子的长度 (k-j+1) ，分析方式同第一种转移。
- 考虑未确定的 (k-j-1) 的形成过程，这里我们用 (g_{k-j-1}) 表示。
因此系数为 (inom{c_1-j}{k-j-1} imes g_{k-j-1} imes (k-j+1)) 。
-
现在我们考虑 (g) 的转移，明确 (g) 的含义为 " 将 (n) 个石柱震为高度连续的（初始）状态数 " 。
其实这个过程很类似于 (f) 的第二种转移。我们只需要枚举一下编号最小的柱子的高度：
这样做的时间复杂度即 (O(n^3)) 。
小结：
- 由于题目限制向后相关，因此进行倒着 DP 。
- 延后考虑某些标准柱的高度的处理方法。
- 转化问题，区分柱子的方法。
- 注意根据题目问题确定转移系数，不要误解为方案数。
代码
#include <cstdio>
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
typedef long long LL;
const int mod = 1e9 + 7, inv2 = ( mod + 1 ) >> 1;
const int MAXN = 2e3 + 5;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
template<typename _T>
_T MAX( const _T a, const _T b )
{
return a > b ? a : b;
}
int f[MAXN][MAXN];
int g[MAXN];
int C[MAXN][MAXN];
int N, M;
bool save[MAXN];
inline int Mul( LL x, int v ) { return x * v % mod; }
inline int Sub( int x, int v ) { return ( x -= v ) < 0 ? x + mod : x; }
inline int Add( int x, int v ) { return ( x += v ) >= mod ? x - mod : x; }
void Init()
{
rep( i, 0, M )
{
C[i][0] = C[i][i] = 1;
rep( j, 1, i - 1 )
C[i][j] = Add( C[i - 1][j], C[i - 1][j - 1] );
}
}
int main()
{
read( N );
rep( i, 1, N ) { int a;
read( a ), save[a] = true;
}
M = N << 1, Init();
g[0] = 1;
rep( i, 1, M ) rep( j, 1, M )
g[i] = Add( g[i], Mul( C[i - 1][j - 1], Mul( j + 1, Mul( g[j - 1], g[i - j] ) ) ) );
f[M + 1][0] = 1; int c0 = 0, c1 = 0;
per( i, M, 1 )
if( save[i] )
{
c1 ++;
rep( j, c0, c1 - 1 )
{
f[i][j] = Add( f[i][j], f[i + 1][j] );
rep( k, 1, c1 - j )
f[i][j + k] = Add( f[i][j + k], Mul( f[i + 1][j], Mul( C[c1 - j - 1][k - 1], Mul( g[k - 1], k + 1 ) ) ) );
}
}
else
{
c0 ++;
rep( j, c0, c1 )
f[i][j] = Add( f[i][j], Mul( f[i + 1][j], j - c0 + 1 ) );
}
rep( i, 1, N ) f[1][N] = Mul( f[1][N], inv2 );
write( f[1][N] ), putchar( '
' );
return 0;
}