#P3554. [Shoi2014]神秘金字塔

    ID: 2672 传统题 6000ms 640MiB 尝试: 31 已通过: 9 难度: 9 上传者: 标签>难度分类省选/NOI-构造与建模对称性分析动态规划轮廓线 DP枚举与搜索状态编码计数 DP数据结构哈希表滚动数组可行性剪枝CF2600By佚名提供

[Shoi2014]神秘金字塔

[SHOI2014] 神秘金字塔

题目描述

考古学家在 CCM 文明遗迹中发现了一座残缺的金字塔。他们已知它由相同的 1×1×11\times1\times1 石块垒成,并满足以下条件。

  1. 每一层的石块在俯视平面内形成一个连通块。除底层之外,每一块石块都由正下方一层的石块支撑。
  2. 每层的俯视形状都左右对称、上下对称,且各层对应的对称轴重合。从任一对称轴向两侧考察,长度或宽度均不增加。
  3. 每层的最大长度和最大宽度相等,且为偶数。

给定石块总数、金字塔总层数及从底到顶的每层最大长度,求满足条件的不同金字塔形状数。各层的形状和叠放位置由俯视格子上的石块高度确定。

输入格式

第一行两个整数 n,hn,h,表示石块总数和金字塔层数。接下来 hh 行,每行一个整数 lil_i,表示从底往上第 ii 层的最大长度,该层的最大宽度也为 lil_i。保证 l1,…,lhl_1,\ldots,l_h 单调不增。

输出格式

一行一个整数,表示满足条件的形状数对 109+710^9+7 取模后的结果。

样例 #1

36 3
6
4
2
1

样例 #2

44 2
6
4
3

下图从上到下展示样例一的唯一形状和样例二的三个形状。每格数字表示该处堆叠的石块数,空白格没有石块。

两个样例的金字塔俯视高度,第一组一种,第二组三种

数据范围

原赛累计分值 条件
10%10\% h=1h=1
30%30\% n≤200n\le200,li≤10l_i\le10,h≤5h\le5
70%70\% n≤800n\le800,li≤20l_i\le20,h≤8h\le8
100%100\% n≤1000n\le1000,2≤li≤202\le l_i\le20,1≤h≤101\le h\le10