Solução Baile de Formatura

Solução por Lucca Siaudzionis

Vamos definir por f(b, g) o número de maneiras formar os pares com b meninos e g meninas. Primeiro, vamos notar que f(x, x) = x! . Suponhamos agora b > g. Vamos, fixado o número de garotas, achar calcular todos os f(b, g):

f(b, g) = g \times ( \ f(b-1, g) + f(b-1, g-1)\ )


//
// baile_de_formatura.cpp
//
// Created by Lucca Siaudzionis on 19/11/14.
// Copyright (c) 2014 Luccasiau. All rights reserved.
//
#include <cstdio>
#define MOD 1000000007
typedef long long lli;
#define MAXN 1010
int g, b;
lli fact[MAXN];
lli ways[MAXN][MAXN];
int main(){
fact[0] = 1LL;
for(int i = 1;i < MAXN;i++)
fact[i] = (lli(i)*fact[i-1]) % MOD;
for(int i = 1;i < MAXN;i++)
ways[1][i] = 1LL,
ways[i][i] = fact[i];
for(int i = 2;i < MAXN;i++)
for(int j = i+1;j < MAXN;j++)
ways[i][j] = (lli(i)*( ways[i][j-1] + ways[i-1][j-1] )) % MOD;
while(scanf("%d %d", &b, &g) && b) printf("%lld\n", ways[g][b]);
return 0;
}

view raw

baile.cpp

hosted with ❤ by GitHub