网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[UVa 11806]拉拉队
成绩 | 开启时间 | 2014年09月19日 星期五 10:07 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:07 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:07 |
输入文件 | Cheerleaders.in | 输出文件 | Cheerleaders.out |
【题目描述】
在大多数专业的体育赛事中,拉拉队总是对观众的娱乐起着相当大的作用(尤其是在休息时,并开始玩之前)世界杯足球也不例外。通常情况下,拉拉队员们组成一个小组,并在场地中央表演,有时她们中有些人被置于边缘以便更接近观众。组织者希望确保每个边至少有一名拉拉队员。对于这个问题,我们将场地建模为一个M* N个矩形网格,共有k名队员。用于放置拉拉队的限制说明如下:
--4条边上每条边至少有一名拉拉队员。需要注意的是,放置一个拉拉队员在一个角落里的网格中相当于同时涵盖两条边。
--一个网格中最多有一名队员。
--所有可用的啦啦队必须被分配给一个网格。也就是说,没有队员可以被排除在外(处于闲置状态)。
【输入格式】
输入第一行为数据组数T(T≤50),每组数据包含3个整数m ,n , k(2≤m,n≤20,k≤500).
【输出格式】
对于每组数据,输出总方案数除以1 000 007的余数。
【样例输入】
2 2 2 1 2 3 2
【样例输出】
Case 1: 0 Case 2: 2
【提示】
相当于:
在一个m行n列的矩形网格里放k个石子,问有多少种放法?每个格子里最多放一个石子,所有石子都要用完,并且第一行,最后一行,第一列,最后一列都得有石子。
【来源】
UVa 11806 , Cheerleaders.
刘汝佳,《算法竞赛入门经典训练指南》表2.2