Cheerleaders UVA - 11806 计数问题

时间:2022-10-01 20:01:15
In most professional sporting events, cheerleaders play a major role in entertaining the spectators. Their
roles are substantial during breaks and prior to start of play. The world cup soccer is no exception.
Usually the cheerleaders form a group and perform at the centre of the eld. In addition to this group,
some of them are placed outside the side line so they are closer to the spectators. The organizers would
like to ensure that at least one cheerleader is located on each of the four sides. For this problem, we
will model the playing ground as an
M
N
rectangular grid. The constraints for placing cheerleaders
are described below:
There should be at least one cheerleader on each of the four sides. Note that, placing a cheerleader
on a corner cell would cover two sides simultaneously.
There can be at most one cheerleader in a cell.
All the cheerleaders available must be assigned to a cell. That is, none of them can be left out.
The organizers would like to know, how many ways they can place the cheerleaders while maintaining
the above constraints. Two placements are different, if there is at least one cell which contains a
cheerleader in one of the placement but not in the other.
Input
The rst line of input contains a positive integer
T
50, which denotes the number of test cases.
T
lines then follow each describing one test case. Each case consists of three nonnegative integers, 2
M
,
N
20 and
K
500. Here
M
is the number of rows and
N
is the number of columns in the grid.
K
denotes the number of cheerleaders that must be assigned to the cells in the grid.
Output
For each case of input, there will be one line of output. It will rst contain the case number followed by
the number of ways to place the cheerleaders as described earlier. Look at the sample output for exact
formatting. Note that, the numbers can be arbitrarily large. Therefore you must output the answers
modulo
1000007.
Sample Input
2
2 2 1
2 3 2
Sample Output
Case 1: 0
Case 2: 2
 
简单的计数问题;
题目所说:第一行,最后一行,第一列,最后一列都得有石子;
设集合A:不在第一行,
集合B:不在最后一行;
集合C:不在第一列;
集合D:不在最后一列;
总集合为S的话,那么我们要求的就是在S中而且不在集合ABCD中的个数;
那我们用二进制来表示,总的数量为2^4=16种情况;
容斥一下就Ok了;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<bitset>
#include<ctime>
#include<deque>
#include<stack>
#include<functional>
#include<sstream>
//#include<cctype>
//#pragma GCC optimize(2)
using namespace std;
#define maxn 2000005
#define inf 0x7fffffff
//#define INF 1e18
#define rdint(x) scanf("%d",&x)
#define rdllt(x) scanf("%lld",&x)
#define rdult(x) scanf("%lu",&x)
#define rdlf(x) scanf("%lf",&x)
#define rdstr(x) scanf("%s",x)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int U;
#define ms(x) memset((x),0,sizeof(x))
const long long int mod = 1e6 + 7;
#define Mod 1000000000
#define sq(x) (x)*(x)
#define eps 1e-4
typedef pair<int, int> pii;
#define pi acos(-1.0)
//const int N = 1005;
#define REP(i,n) for(int i=0;i<(n);i++)
typedef pair<int, int> pii;
inline ll rd() {
ll x = 0;
char c = getchar();
bool f = false;
while (!isdigit(c)) {
if (c == '-') f = true;
c = getchar();
}
while (isdigit(c)) {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return f ? -x : x;
} ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a%b);
}
int sqr(int x) { return x * x; } /*ll ans;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1; y = 0; return a;
}
ans = exgcd(b, a%b, x, y);
ll t = x; x = y; y = t - a / b * y;
return ans;
}
*/ int c[503][503];
int n, m, k;
void init() {
c[0][0] = 1;
for (int i = 0; i <= 503; i++) {
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; j++)c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
} int main() {
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T; cin >> T;
init(); int tot = 0;
while (T--) {
tot++;
cin >> n >> m >> k;
cout << "Case " << tot << ": ";
int sum = 0;
for (int i = 0; i < 16; i++) {
int bk = 0;
int r = n, C = m;
if (i & 1) { bk++; r--; }
if (i & 2) { bk++; r--; }
if (i & 4) { bk++; C--; }
if (i & 8) { bk++; C--; }
if (bk % 2) {
sum = (sum + mod - c[C*r][k]) % mod;
}
else sum = (sum + c[C*r][k]) % mod;
}
cout << sum << endl;
}
return 0;
}

Cheerleaders UVA - 11806 计数问题的更多相关文章

  1. Cheerleaders UVA - 11806

    题目大意是: 在一个m行n列的矩形网格中放置k个相同的石子,问有多少种方法?每个格子最多放一个石子,所有石子都要用完,并且第一行.最后一行.第一列.最后一列都要有石子. 容斥原理.如果只是n * m放 ...

  2. Cheerleaders UVA - 11806(容斥&plus;二进制技巧)

    #include <iostream> #include <cstdio> #include <sstream> #include <cstring> ...

  3. uva 11806 Cheerleaders

    // uva 11806 Cheerleaders // // 题目大意: // // 给你n * m的矩形格子,要求放k个相同的石子,使得矩形的第一行 // 第一列,最后一行,最后一列都必须有石子. ...

  4. UVA&period;11806 Cheerleaders &lpar;组合数学 容斥原理 二进制枚举&rpar;

    UVA.11806 Cheerleaders (组合数学 容斥原理 二进制枚举) 题意分析 给出n*m的矩形格子,给出k个点,每个格子里面可以放一个点.现在要求格子的最外围一圈的每行每列,至少要放一个 ...

  5. UVA 11806 Cheerleaders dp&plus;容斥

    In most professional sporting events, cheerleaders play a major role in entertaining the spectators. ...

  6. UVa 11806 Cheerleaders (容斥原理&plus;二进制表示状态)

    In most professional sporting events, cheerleaders play a major role in entertaining the spectators. ...

  7. uva 11806 Cheerleaders (容斥)

    http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&p ...

  8. UVA 11806 Cheerleaders (组合&plus;容斥原理)

    自己写的代码: #include <iostream> #include <stdio.h> #include <string.h> /* 题意:相当于在一个m*n ...

  9. UVA 11806 Cheerleaders &lpar;容斥原理&rpar;

    题意 一个n*m的区域内,放k个啦啦队员,第一行,最后一行,第一列,最后一列一定要放,一共有多少种方法. 思路 设A1表示第一行放,A2表示最后一行放,A3表示第一列放,A4表示最后一列放,则要求|A ...

随机推荐

  1. maven里的modelVersion

    modelVersion 描述这个POM文件是遵从哪个版本的项目描述符

  2. JVM调优-关于jvm的一些基本概念

    1.数据类型 java体系中,数据类型可分为2类:基本类型和引用类型.基本类型保存变量原始值,即:他代表的值就是数值本身: 而引用类型的变量保存引用值."引用值"代表某个对象的引用 ...

  3. 对EJB返回的AaaryList显示到table的处理方法

      1. ArrayList --> Object[]        ArrayList x = new ArrayList();        int i = x.size();        ...

  4. Socket规划中的局域网内测试

    前面提到的Socket信息及文件传输软件,如何测试和使用它? 事实上仅仅要推断client及server的局域网连通就可以. 1.Server在cmd下输入 ipconfig/all获得IP地址或者本 ...

  5. &lbrack;转载&rsqb; 基于zookeeper、连接池、Failover&sol;LoadBalance等改造Thrift 服务化

    转载自http://blog.csdn.net/zhu_tianwei/article/details/44115667 http://blog.csdn.net/column/details/sli ...

  6. 企业Nginx&plus;Keepalived双主架构案例实战

    通过上一次课程的学习,我们知道Nginx+keepalived主从配置,始终有一台服务器处于空余状态,那如何更好的利用起来呢,我们需要借助Nginx+keepalived双主架构来实现,如下图通过改装 ...

  7. 记录mysql安装过程遇到问题

    1. 远程连接授权 登陆mysql数据库    (如果安装在系统盘可以直接命令, 否则要切换到安装目录..bin/) mysql -u root -p mysql> use mysql;   - ...

  8. &lbrack;CQOI2016&rsqb;K远点对

    嘟嘟嘟 做过[国家集训队]JZPFAR这道题的话,这题就不难了. 我们维护一个长度为\(k\)的小根堆,在加入第\(i\)个点之前,用\([1, i - 1]\)这些点离点\(i\)的距离更新答案.这 ...

  9. mysql中存储过程

    存储过程procedure 存储过程,其本质还是函数——但其规定:不能有返回值: 定义形式: 说明: 1,in:用于设定该变量是用来“接收实参数据”的,即“传入”:默认不写,就是in 2,out:用于 ...

  10. Linux学习和ROS安装(1)

    参考文档:https://www.cnblogs.com/liu-fa/p/5779206.html#undefined 系统环境:Window7 64bit+VMware11 ubuntu-gnom ...