「JOISC 2020 Day2」遗迹
crashed
·
·
题解
题目
点这里看题目。
分析
懂了懂了，数数题都是毒瘤。
考虑我们可以怎么去震柱子。显然我们可以从高往低去震，但是这样分析无法导出一个解法。
另一个方式就是从后往前去震；这样我们可以导出一个结论：
如果当前柱子之后有高度为 1\sim h 的柱子各一根，那么当前柱子及之前的柱子，如果高度 \le h，都会被直接震没。
因此我们可以将最大的 h 看作 " 高度阈值 " ，把那 1\sim h 的 h 个柱子称为 " 标准柱 " 。
考虑一个 DP ：
为了便于转移，设两个参数 $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}$。
计算系数，有如下几个部分：
- 选定标准柱的位置 $\binom{c_1-j}{k-j-1}$。
- 确定当前柱子的长度 $k-j+1$，分析方式同第一种转移。
- 考虑未确定的 $k-j-1$ 的形成过程，这里我们用 $g_{k-j-1}$ 表示。
因此系数为 $\binom{c_1-j}{k-j-1}\times g_{k-j-1}\times (k-j+1)$。
现在我们考虑 $g$ 的转移，明确 $g$ 的含义为 " 将 $n$ 个石柱震为高度连续的（初始）状态数 " 。
其实这个过程很类似于 $f$ 的第二种转移。我们只需要枚举一下编号最小的柱子的高度：
$$
g_n=\sum_{i=1}^{n}\binom{n-1}{i-1}\times (i+1)\times g_{i-1}\times g_{n-i}
$$
这样做的时间复杂度即 $O(n^3)$。
# 代码
```cpp
#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( '\n' );
return 0;
}
```