Skip to Content
CTRL K

Distributing Apples

Pista 1

Puede sonar extraño, pero intentemos representar una distribución poniendo a todos los niños y las manzanas en una sola línea.

Pista 2

A partir de la primera pista, deberíamos haber notado que cada distribución se puede representar haciendo que cada niño posea un intervalo de las manzanas. Ahora queda contar de cuántas formas se pueden colocar los niños entre las manzanas.

Solución

Explicación

Para tener una idea más ilustrativa del problema dado, consideremos n+m−1n + m - 1 bolas blancas en una fila. De esas n+m−1n + m - 1 bolas blancas, se eligen n−1n - 1 para colorearlas de negro como separadores, lo que nos da exactamente nn segmentos de bolas blancas (posiblemente vacíos). Hay

(n+m−1n−1) \binom{n + m - 1}{n - 1}

formas de elegir las bolas a colorear de negro.

Las formas de colorear n−1n - 1 bolas de negro corresponden a las formas de distribuir esas mm manzanas a nn niños, porque la cantidad de bolas blancas en un segmento corresponde a la cantidad de manzanas dadas a un niño.

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const ll MOD = 1e9 + 7;
const int MAXN = 2e6;
 
vector<ll> fac(MAXN, 1);
vector<ll> inv(MAXN, 1);
 
/**
 * Calcula x^n módulo m en tiempo O(log p).
 * Ver también: https://usaco.guide/gold/modular
 */
ll binpow(ll x, ll n, ll m) {
	x %= m;
	ll res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % m; }
		x = x * x % m;
		n /= 2;
	}
	return res;
}
 
ll binom(int n, int k) { return fac[n] * inv[k] % MOD * inv[n - k] % MOD; }
 
int main() {
	for (int i = 2; i < MAXN; i++) { fac[i] = i * fac[i - 1] % MOD; }
 
	// Calcular el inverso modular con exponenciación
	inv[MAXN - 1] = binpow(fac[MAXN - 1], MOD - 2, MOD);
	// Calcular el inverso modular con la definición factorial
	for (int i = MAXN - 2; i > 0; i--) { inv[i] = (i + 1) * inv[i + 1] % MOD; }
 
	int n, m;
	cin >> n >> m;
 
	cout << binom(n + m - 1, n - 1) << endl;
}
import java.io.*;
import java.util.*;
 
public class DistributingApples {
	static final long MOD = (long)1e9 + 7;
	static final int MAXN = (int)2e6;
 
	static long[] fac = new long[MAXN];
	static long[] inv = new long[MAXN];
 
	/**
	 * Calcula x^n módulo m en tiempo O(log p).
	 * Ver también: https://usaco.guide/gold/modular
	 */
	static long binpow(long x, long n, long m) {
		x %= m;
		long res = 1;
		while (n > 0) {
			if (n % 2 == 1) { res = res * x % m; }
			x = x * x % m;
			n /= 2;
		}
		return res;
	}
 
	static long binom(int n, int k) { return fac[n] * inv[k] % MOD * inv[n - k] % MOD; }
 
	public static void main(String[] args) throws IOException {
		fac[0] = fac[1] = 1;
		for (int i = 2; i < MAXN; i++) { fac[i] = i * fac[i - 1] % MOD; }
 
		inv[0] = 1;
		// Calcular el inverso modular con exponenciación
		inv[MAXN - 1] = binpow(fac[MAXN - 1], MOD - 2, MOD);
		// Calcular el inverso modular con la definición factorial
		for (int i = MAXN - 2; i > 0; i--) { inv[i] = (i + 1) * inv[i + 1] % MOD; }
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
 
		System.out.println(binom(n + m - 1, n - 1));
	}
}
MOD = int(1e9) + 7
MAXN = int(2e6)
 
fac: list = [1 for _ in range(MAXN)]
inv: list = [1 for _ in range(MAXN)]
 
 
def binpow(x: int, n: int, m: int) -> int:
	"""
	Calcula x^n módulo m en tiempo O(log p).
	Ver también: https://usaco.guide/gold/modular
	"""
	x %= m
	res: int = 1
	while n > 0:
		if n % 2 == 1:
			res = res * x % m
		x = x * x % m
		n //= 2
 
	return res
 
 
def binom(n: int, k: int) -> int:
	return fac[n] * inv[k] % MOD * inv[n - k] % MOD
 
 
for i in range(2, MAXN):
	fac[i] = i * fac[i - 1] % MOD
 
# Calcular el inverso modular con exponenciación
inv[MAXN - 1] = binpow(fac[MAXN - 1], MOD - 2, MOD)
# Calcular el inverso modular con la definición factorial
for i in reversed(range(1, MAXN - 1)):
	inv[i] = (i + 1) * inv[i + 1] % MOD
 
(n, m) = map(int, input().split())
print(binom(n + m - 1, n - 1))
Fundamentos