C. The World is a Theatre
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
There are n boys and m girls attending a theatre club. To set a play "The Big Bang Theory", they need to choose a group containing exactly t actors containing no less than 4 boys and no less than one girl. How many ways are there to choose a group? Of course, the variants that only differ in the composition of the troupe are considered different.
Perform all calculations in the 64-bit type: long long for С/С++, int64 for Delphi and long for Java.
Input
The only line of the input data contains three integers n, m, t (4 ≤ n ≤ 30, 1 ≤ m ≤ 30, 5 ≤ t ≤ n + m).
Output
Find the required number of ways.
Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.
Examples
input
Copy
5 2 5
output
Copy
10
input
Copy
4 3 5
output
Copy
3
容斥一下，先算出来和为t的所有情况数，然后减去男生0～3个的情况数以及女生0个的情况数，再加上男生0～3个女生0个且和为t的情况数。牛客可以用int128草过，但cf好像不支持int128。这种不需要取模的组合数计算如果直接暴力的话由于涉及阶乘很可能会溢出，所以最好用杨辉三角进行计算。
//0~3男和0～1女
#include <bits/stdc++.h>
#define ll long long
#define int __int128
#define maxn 100005
using namespace std;
int factorial(int t) {
if(t == 0 || t == 1) return 1;
return t * factorial(t - 1);
}
int C(int n,int m) {
return factorial(n) / (factorial(m) * factorial(n - m)) ;//组合数计算公式
}
// int C(int n, int m)//组合数
// {
// if(m < 0) return 0;
// if(m < n - m) m = n - m;//m越大 n-m越小，越有利
// long long ans = 1;
// for(ll i = m + 1; i <= n; i++)
// ans *= i;
// for(ll i = 1; i <= n - m; i++)
// ans /= i;
// return ans;
// }
inline __int128 read()
{
int X=0,w=0; char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
return w?-X:X;
}
void print(__int128 x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)print(x/10);
putchar(x%10+'0');
}
signed main() {
int n, m, t;
n = read(), m = read(), t = read();
int ans = 0;
for(int i = 0; i <= n; i++) {
if(t - i >= 0 && t - i <= m) {
ans += C(n, i) * C(m, t - i);
}
}
for(int i = 0; i <= 3; i++) {
int j = t - i;
if(j >= 0 && j <= m) {
ans -= C(n, i) * C(m, j);
}
}
for(int i = 0; i <= 0; i++) {
int j = t - i;
if(j >= 0 && j <= n) {
ans -= C(m, i) * C(n, j);
}
}
for(int i = 0; i <= 3; i++) {
for(int j = 0; j <= 0; j++) {
if(i + j != t) continue;
ans += C(n, i) * C(m, j);
}
}
print(ans);
return 0;
}
杨辉三角代码：
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 30;
long long C[N + 5][N + 5];
int main()
{
for (int i = 0; i <= N;i++)
C[i][0] = C[i][i] = 1;
for (int i = 1; i <= N;i++)
for (int j = 1; j < i;j++)
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
int n, m, t;
scanf("%d%d%d", &n, &m, &t);
long long ans = 0;
for (int i = 4; i <= t - 1; i++)
if (m >= t - i && n >= i)
ans += C[n][i] * C[m][t - i];
printf("%lld", ans);
return 0;
}