UVA 11806 Cheerleaders (容斥原理)

时间：2024-01-05 14:40:56

题意

一个n*m的区域内，放k个啦啦队员，第一行，最后一行，第一列，最后一列一定要放，一共有多少种方法。

思路

设A1表示第一行放，A2表示最后一行放，A3表示第一列放，A4表示最后一列放，则要求|A1∧A2∧A3∧A4|

由容斥原理可知|∪Ai| = Σ|Ai| - Σ|Ai∧Aj| + …… (+-)|Ai∧Aj∧……∧Ak|.

再由德摩根定律得：∧Ai = Cu(∪Cu(Ai))，所以|∧Ai| = S - |∪Cu(Ai)|.（Cu表示集合的非）

然后令A表示不放第一行，B表示不放最后一行，C表示不放第一列，D表示不放最后一列。

ANS = ALL-A-B-C-D+AB+AC+AD+BC+BD-ABC-ABD-BCD+ABCD

代码

#include

#include

#include

#include

#include

#include

#define MID(x,y) ((x+y)/2)

#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;

const int MAXNUM = 505;

int C[MAXNUM][MAXNUM];

void cal_C(int n, int mod){

    mem(C, 0);

    C[0][0] = 1;

    for (int i = 1; i

相关文章