题目
门前有一道很深的沟，呈一排方格状。其余部分都平平整整的，唯独有连续的 (n) 格坑坑洼洼。这些坑洼的格子被从 1 开始编号，从沟底开始算，第 (i) 格的高度为一个正整数 (h_i)。
天下大雨，于是坑洼的部分会产生积水，而平整的部分的水会被直接排掉。考虑某个竖直切面，如果某个空白的点左侧和右侧均有格子高度不低于它，那么这个点就会积水。显然，如果格子高度都是整数，那么积水体积也会是整数。
坑洼的地面不好看，你决定平整某些格子——即，选出一些格子使其高度变为 0。但是，你发现这可是个体力活，你只能平整恰好 (k) 个格子。现在你想知道，在所有的 (inom{n}{k}) 种施工方案中，有多少种方案会使得最终的积水体积是偶数？
数据范围：对于 (100\%) 的数据，满足 (1le nle 25000,1le h_ile 10^9,1le kle min{25,n-1})。
分析
对于最终的高度局面，我们可以得到积水总体积为：
注意到计算过程只与前缀、后缀最大值有关，因此可以设计一种 DP：
设 (f_{i,k,p,s,0/1}) 表示考虑了前 (i) 个格子，当前有 (k) 个被平整，此时前缀最大高度为 (p)，后缀存在一个高度为 (s) 的格子，若积水体积为偶数/奇数时的方案总数。
重要的观察：由于最多平整 (k) 个格子，所以说，(p,s) 分别最多只有 (k+1) 种取值。所以这个 DP 是 (O(nk^3)) 的。
这个复杂度虽然已经很不错了，但是我们还需要继续优化。
注意到，最终高度局面中，最高的格子一定不会贡献任何积水，但是最高的格子一定可以当作边界来用：
例如，中间的黄色格子就是最高的；当我们考虑前缀红格子的时候，我们可以假定后面存在一个更高的格子；同样的，考虑后缀绿格子的时候，我们也可以假定前面存在一个更高的格子。
因此可以重新设计状态：设 (g_{i,j,k,0/1}) 表示考虑了 (i) 个格子之后，前缀最大高度为 (j)，已经使用了 (k) 次平整机会，此时积水体积为偶数/奇数的方案总数。正向反向都做一遍，然后枚举最大值合并即可。
枚举最大值需要考虑多个最大值的情况——因此我们总是在枚举第一个最大值。
这个做法还可以优化！
对于所有方案，我们可以将它们划分为两类——积水体积为偶数的和积水体积为奇数的。注意到，我们已经知道了两类方案数的和，我们只需要再知道它们的差即可。因此我们可以抛弃 DP 的最后一维，而直接维护 偶数 - 奇数 即可。
小结：
- 注意关键性质，例如本题中取值可能性的性质；
- 不一定需要从头 DP 到尾，如果问题有一些特殊的信息可以枚举，那么我们可以在 DP 外进行枚举；
- 充分利用已知信息；
代码
#include <set>
#include <cstdio>
#include <vector>
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
const int mod = 1e9 + 7;
const int MAXN = 25005, MAXK = 30;
template<typename _T>
void read( _T &x )/*{{{*/
{
x = 0; char s = getchar(); bool f = false;
while( ! ( '0' <= s && s <= '9' ) ) { f = s == '-', s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
if( f ) x = -x;
}/*}}}*/
template<typename _T>
void write( _T x )/*{{{*/
{
if( x < 0 ) putchar( '-' ), x = -x;
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[2][MAXK][MAXK];
int g[MAXN][MAXK][MAXK];
int suF[MAXK], suG[MAXK];
std :: set<int> s;
std :: vector<int> pref[MAXN], suff[MAXN];
int h[MAXN], stk[MAXN];
int N, K;
inline int Qkpow( int, int );
inline int Mul( int x, int v ) { return 1ll * x * v % mod; }
inline int Inv( const int a ) { return Qkpow( a, mod - 2 ); }
inline int Add( int x, int v ) { return ( x += v ) >= mod ? x - mod : x; }
inline void Upt( int &x, const int v ) { x = Add( x, v ); }
inline int Qkpow( int base, int indx )/*{{{*/
{
int ret = 1;
while( indx )
{
if( indx & 1 ) ret = Mul( ret, base );
base = Mul( base, base ), indx >>= 1;
}
return ret;
}/*}}}*/
int main()
{
read( N ), read( K );
rep( i, 1, N ) read( h[i] );
rep( i, 0, N )
{
s.insert( h[i] );
if( s.size() > ( unsigned ) K + 1 ) s.erase( s.begin() );
for( auto x : s ) pref[i].push_back( x );
}
s.clear();
per( i, N + 1, 1 )
{
s.insert( h[i] );
if( s.size() > ( unsigned ) K + 1 ) s.erase( s.begin() );
for( auto x : s ) suff[i].push_back( x );
}
g[N + 1][0][0] = 1;
per( i, N + 1, 2 ) // transition for g{{{
{
int p1 = 0, p2 = 0;
int n = suff[i].size(), m = suff[i - 1].size();
for( int j = 0 ; j < n ; j ++ )
for( int k = 0 ; k <= K ; k ++ )
{
if( ! g[i][j][k] ) continue;
int curH = MAX( suff[i][j], h[i - 1] );
for( ; p1 < m && suff[i - 1][p1] < curH ; p1 ++ );
bool coe = ( curH & 1 ) ^ ( h[i - 1] & 1 );
Upt( g[i - 1][p1][k], coe ? mod - g[i][j][k] : g[i][j][k] );
if( k == K ) continue; curH = suff[i][j];
for( ; p2 < m && suff[i - 1][p2] < curH ; p2 ++ );
coe = curH & 1, Upt( g[i - 1][p2][k + 1], coe ? mod - g[i][j][k] : g[i][j][k] );
}
}/*}}}*/
int ans = 0;
int pre = 1, nxt = 0;
f[nxt][0][0] = 1;
rep( i, 0, N - 1 )
{
// Calculation for answer
rep( k, 0, K ) suF[k] = suG[k] = 0;
int n = pref[i].size(), m = suff[i + 2].size();
for( int j = 0 ; j < n && pref[i][j] < h[i + 1] ; j ++ )
rep( k, 0, K ) Upt( suF[k], f[nxt][j][k] );
for( int j = 0 ; j < m && suff[i + 2][j] <= h[i + 1] ; j ++ )
rep( k, 0, K ) Upt( suG[k], g[i + 2][j][k] );
for( int j = 0 ; j <= K ; j ++ )
Upt( ans, Mul( suF[j], suG[K - j] ) );
// transition
int p1 = 0, p2 = 0; pre ^= 1, nxt ^= 1;
n = pref[i].size(), m = pref[i + 1].size();
for( int j = 0 ; j < m ; j ++ )
for( int k = 0 ; k <= K ; k ++ )
f[nxt][j][k] = 0;
for( int j = 0 ; j < n ; j ++ )
for( int k = 0 ; k <= K ; k ++ )
{
if( ! f[pre][j][k] ) continue;
int curH = MAX( pref[i][j], h[i + 1] );
for( ; p1 < m && pref[i + 1][p1] < curH ; p1 ++ );
bool coe = ( curH & 1 ) ^ ( h[i + 1] & 1 );
Upt( f[nxt][p1][k], coe ? mod - f[pre][j][k] : f[pre][j][k] );
if( k == K ) continue; curH = pref[i][j];
for( ; p2 < m && pref[i + 1][p2] < curH ; p2 ++ );
coe = curH & 1, Upt( f[nxt][p2][k + 1], coe ? mod - f[pre][j][k] : f[pre][j][k] );
}
}
int all = 1;
rep( i, 1, K ) all = Mul( all, Mul( Inv( i ), N - i + 1 ) );
write( Mul( Inv( 2 ), Add( all, ans ) ) ), putchar( '
' );
return 0;
}