查看CodeForces/131C的源代码 ←CodeForces/131C

[[分类:组合数学]]
==摘要==
{{信息题|The World is a Theatre|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}70200#problem/I|2|100|遗漏情况|4|time=2015-02-14 15:52:05}}
*来自寒假练习：[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70200 Special Round for Valentine's Day] I题
*原题链接：http://codeforces.com/problemset/problem/131/C
==题意==
有b男g女，选出k个人，使得其中有男>=4女>=1（每个人视作不同）。
==题解==
高三的排列组合题呀……最简单的想法是排除法：

<m>C_{b+g}^{k}-C_{b}^{k}-C_{b}^{1}*C_{g}^{k-1}-C_{b}^{2}*C_{g}^{k-2}-C_{b}^{3}*C_{g}^{k-3}-C_{g}^{k}</m>

蠢得要死第一次一不小心把全是女生的情况漏了……
==代码==
{{折叠|131C.cpp代码已折叠
|<pre>
#include<cstdio>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<vector>
using namespace std;
#define si(n) scanf("%d",&n)
typedef unsigned long long ll;
#define ci const int&
ll c[100][100]={};
ll C(ci x,ci y)
{
    if(!x||!y||x==y)return 1;
    if(x<y)return 0;
    if(c[x][y])return c[x][y];
    return c[x][y]=C(x-1,y)+C(x-1,y-1);
}
int main()
{
    int b,g,k;
    scanf("%d%d%d",&b,&g,&k);
    if(b>=4&&g>=1&&k>=5)
        printf("%I64d",C(b+g,k)-C(b,k)-C(b,1)*C(g,k-1)-C(b,2)*C(g,k-2)-C(b,3)*C(g,k-3)-C(g,k));//fixed：漏了C(g,k)//
    else
        printf("0");
    return 0;
}
</pre>
|code131C}}