#P7220. [2023省队模拟]雨
[2023省队模拟]雨
题目描述
有一个积雨装置,底板为 ,底板上有 个面积为 的凹槽。第 个凹槽上嵌有一个高度为 的长方体。
从正面观察时, 个长方体依次排成一行。装置前后都有宽度为 、高度足够大的挡板,左右两侧没有挡板。
雨量可以视作无限。下雨足够久后,装置中最终积蓄的雨水量是确定的,记为 。例如,,从左到右的高度分别为 ,则只有第二个位置会积水,水面高度为 ,所以 。
现在需要移除恰好 个长方体,被移除的位置的高度变为 。问有多少种移除方式使 为偶数,答案对 取模。
输入格式
第一行两个整数 。
第二行 个正整数 。
输出格式
输出一行一个整数,表示答案对 取模后的结果。
样例输入 1
4 1
4 1 3 4
样例输出 1
2
分别移除第 个长方体时, 依次为 ,其中两种方案的 为偶数。
样例输入 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 | 10 | |
| 2 | 5 | |
| 3 | 特殊性质 A, | 15 |
| 4 | 20 | |
| 5 | ||
| 6 | 无特殊限制 | 30 |
特殊性质 A:设 ,则所有满足 的位置构成一个连续区间 ,且 。