#P2616. SPOJ PERIODNI

    ID: 1671 传统题 1000ms 512MiB 尝试: 295 已通过: 81 难度: 8 上传者: 标签>CF2400提高+/省选-笛卡尔树单调栈树形 DP计数 DP阶乘逆元预处理排列数计算子树合并剪除无效容量

SPOJ PERIODNI

题目描述

棋盘由 NN 列组成,各列底边对齐。第 ii 列从下往上有 hih_i 个格子,即第 ii 列的第 11 到第 hih_i 行存在,其余行没有格子。

在棋盘的不同格子里放恰好 KK 个车。两个车位于同一列时会相互攻击。若它们位于同一行,只有当两者之间这一行的格子都存在时才会相互攻击。也就是说,棋盘中的缺口会阻断横向攻击。

求使任意两个车都不会相互攻击的放置方案数。车之间没有编号,同一组位置只算一种方案。

原题棋盘与攻击关系示意

输入格式

第一行包括两个正整数 NN 和 KK,表示了棋盘的列数和放的车数。 第二行包含 NN 个正整数,表示了棋盘每列的高度。

输出格式

包括一个非负整数,表示有多少种放置的方案,输出答案mod  1000000007\mod 1000000007 后的结果即可。

示例

输入1

5 2 
2 3 1 2 4

输出1

43

提示

对于 100%100\% 的数据,有 N≤500N \leq 500,K≤500K \leq 500,hi≤1000000h_i \leq 1000000。

原题(SPOJ PERIODNI)