#P16865. SPOJ PERIODNI

    ID: 16075 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-分治算法树上背包计数 DPPascal 递推排列数计算乘法原理

SPOJ PERIODNI

题目描述

Luka 画了一张特殊表格,共有 NN 列,每列从底部对齐,但高度可能不同。

他要在其中放置 KK 个相同的“稀有气体”标记,并要求任意两个标记都不能“靠得太近”。

两个格子被认为“靠近”,当且仅当:

  • 它们位于同一列;或
  • 它们位于同一行,并且这两个格子之间的所有格子都存在。

因此,同一行中如果中间因为某列高度不足而出现断层,则断层两侧的两个格子并不算靠近。

求放置 KK 个标记的方案数,答案对 1 000 000 0071\,000\,000\,007 取模。

输入格式

第一行两个整数 N,KN,K:

1≤N,K≤500.1\le N,K\le500.

第二行 NN 个正整数 H1,H2,…,HNH_1,H_2,\dots,H_N,表示每列高度:

1≤Hi≤106.1\le H_i\le10^6.

输出格式

输出一个整数,表示合法放置方案数对 1 000 000 0071\,000\,000\,007 取模后的结果。

样例

5 2
2 3 1 2 4
43

原题示意图