| 比赛场次 | 146 |
|---|---|
| 比赛名称 | 20120707 |
| 比赛状态 | 已结束比赛成绩 |
| 开始时间 | 2012-07-07 08:00:00 |
| 结束时间 | 2012-07-07 12:00:00 |
| 开放分组 | 全部用户 |
| 注释介绍 | 2012暑假培训A班 |
| 题目名称 | 奇怪的棋盘 |
|---|---|
| 输入输出 | boarda.in/out |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 128 MiB |
| 测试点数 | 10 简单对比 |
| 用户 | 结果 | 时间 | 内存 | 得分 |
|---|---|---|---|---|
 Citron酱 |
AAAAATTTTT | 10.113 s | 2.20 MiB | 50 |
 SnowDancer |
AAAATEEEEE | 2.414 s | 32.17 MiB | 40 |
 ZhouHang |
AAAWWWWWWW | 0.121 s | 45.55 MiB | 30 |
 isabella |
AATTTTTTEE | 12.129 s | 0.41 MiB | 20 |
 Makazeu |
AWEEWWWWEE | 0.790 s | 4.10 MiB | 10 |
 fuhao |
WWWWWWWWWW | 0.003 s | 0.17 MiB | 0 |
 CC |
WWWWWWWWWW | 0.010 s | 1.26 MiB | 0 |
 Czb。 |
EEEEEEEEEE | 1.569 s | 7.92 MiB | 0 |
 czp |
RRTTTTTTTT | 16.022 s | 0.17 MiB | 0 |
【题目描述】
现在有一张n列的棋盘，每一列的高度为h_i，每一列的底在同一水平线上。
然后你需要在这个棋盘上放k个象棋里的车，使得他们互不攻击，问一共有多少种不同的摆放方法。注意两个车可以互相攻击当且仅当他们处在同一行或者同一列，而且中间的棋盘没有空缺。
上图是一张合法的棋盘，每列高度分别为2，3，1，2，4，而且两个b可以互相攻击，但是a不会互相攻击。
【输入格式】
第一行两个整数，n和k，分别表示棋盘列数和需要放的车的个数
接下来一行n个正整数h_i，表示每一列的高度
【输出格式】
一行一个整数，表示方案数。结果对1000000007取模
【样例输入1】
3 3
2 1 3
【样例输出1】
2
【样例输入2】
5 2
2 3 1 2 4
【样例输出2】
43
【数据范围】
对于40%的数据，0 <= n,k,h_i <= 15
对于70%的数据，0 <= n,k,h_i <= 100
对于100%的数据，0 <= n, k <= 500, 0 <= h_i <= 1000000
【时限】
2s