#P7220. [2023省队模拟]雨

    ID: 7054 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-前后缀状态分解有限候选集缩减线性 DP计数 DP奇偶性分析滚动数组添加哨兵

[2023省队模拟]雨

题目描述

有一个积雨装置,底板为 1×n1\times n,底板上有 nn 个面积为 1×11\times1 的凹槽。第 ii 个凹槽上嵌有一个高度为 hih_i 的长方体。

从正面观察时,nn 个长方体依次排成一行。装置前后都有宽度为 nn、高度足够大的挡板,左右两侧没有挡板。

雨量可以视作无限。下雨足够久后,装置中最终积蓄的雨水量是确定的,记为 ff。例如,n=3n=3,从左到右的高度分别为 3,1,43,1,4,则只有第二个位置会积水,水面高度为 33,所以 f=2f=2。

现在需要移除恰好 kk 个长方体,被移除的位置的高度变为 00。问有多少种移除方式使 ff 为偶数,答案对 109+710^9+7 取模。

输入格式

第一行两个整数 n,kn,k。

第二行 nn 个正整数 h1,h2,…,hnh_1,h_2,\ldots,h_n。

输出格式

输出一行一个整数,表示答案对 109+710^9+7 取模后的结果。

样例输入 1

4 1
4 1 3 4

样例输出 1

2

分别移除第 1,2,3,41,2,3,4 个长方体时,ff 依次为 0,5,7,20,5,7,2,其中两种方案的 ff 为偶数。

样例输入 2

7 1
2 5 2 4 1 6 2

样例输出 2

4

样例输入 3

15 8
8 2 7 6 7 3 6 9 2 5 4 3 5 4 8

样例输出 3

3246

数据范围与约定

对于全部数据,1≤n≤2.5×1041\le n\le2.5\times10^4,0≤k≤min⁡{n−1,25}0\le k\le\min\{n-1,25\},1≤hi≤1091\le h_i\le10^9。

子任务 数据范围 分值
1 1≤n≤201\le n\le20 10
2 k=0k=0 5
3 特殊性质 A,n≤500n\le500 15
4 n≤500n\le500 20
5 n≤1000n\le1000
6 无特殊限制 30

特殊性质 A:设 v=max⁡ihiv=\max_i h_i,则所有满足 hi=vh_i=v 的位置构成一个连续区间 [l,r][l,r],且 r−l+1≥30r-l+1\ge30。