首页 > 其他 > 详细

G - Cheerleaders (UVA - 11806)

时间:2018-02-14 15:31:25      阅读:28      评论:0      收藏:0      [点我收藏+]

标签:brush   end   判断   最后一行   for   gpo   cpp   using   mes   

- 题目大意

     本题大致意思是讲:给定一个广场,把它分为M行N列的正方形小框。现在给定有K个拉拉队员,每一个拉拉队员需要站在小框内进行表演。但是表演过程中有如下要求:

(1)每一个小框只能站立一个拉拉队员;

(2)广场的第一行,最后一行,第一列,最后一列都至少站有一个拉拉队员;

(3)站在广场的四个角落的拉拉队员可以认为是同时占据了一行和一列。

- 解题思路

  利用容斥原理来解决,将不满足条件的一一剔除,(我的方法比较笨重,如果选择二进制来判断做起来就比较轻松了)。

- 代码

#include<iostream>
using namespace std;
const long long mod =1000007;
const int MAX = 500;
long long num[MAX][MAX];
void zh()
{
	for (long long i = 0; i < MAX; i++) {
		num[i][0] = num[i][i] = 1;
		for (long long j = 1; j < i; j++) {
			num[i][j] = (num[i - 1][j - 1] + num[i - 1][j]) % mod;
		}
	}
 }
int main()
{
	int t, m, n,k;
	cin >> t;
	zh();
	for (int i = 1; i <= t; i++)
	{
		long long sum = 0;
		cin >> n>> m>>k;
		cout << "Case " << i << ": ";
		if (k > m*n)
		{
			cout << sum << endl;
			continue;
		}
			sum= (num[m*n][k]-(2 * (num[(n - 1)*m][k] + num[n*(m - 1)][k]) - (num[(n - 2)*m][k] + num[n*(m - 2)][k]) + 2 * (num[(n - 1)*(m - 2)][k] + num[(n - 2)*(m - 1)][k]) - num[(n - 2)*(m - 2)][k]-4 * num[(n - 1)*(m - 1)][k]));
			while (sum < 0)
				sum += mod;
			sum %= mod;
			cout << sum << endl;
    
	}
	return 0;
}

  

G - Cheerleaders (UVA - 11806)

标签:brush   end   判断   最后一行   for   gpo   cpp   using   mes   

原文:https://www.cnblogs.com/alpacadh/p/8448365.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号