Skip to Content
CTRL K

Creating Strings II

Explicación

Esta estrategia se conoce como el teorema multinomial .

Esencialmente estamos contando cuántos strings distintos podemos formar permutando las letras del string. Notar que si hay caracteres repetidos en el string, permutar esos caracteres en su lugar cuenta como el mismo string porque las letras son indistinguibles.

Por ejemplo, consideremos el string aabaab, y supongamos que denotamos las aa que aparecen en el string en el orden en que aparecen, de modo que el string original se convierte en a1a2ba_1a_2b. Una permutación posible es a2a1ba_2a_1b. Cuando quitamos estos subíndices, estos dos strings se vuelven la misma cosa.

Para tener esto en cuenta, recorremos cada letra que aparece en el string y dividimos por la cantidad de arreglos entre sus ocurrencias. El total de permutaciones es n!n!. La cantidad de formas en que una letra puede permutarse es también el factorial de la cantidad de veces que aparece en el string.

Implementación

Complejidad temporal: O(MAXN∗log⁡(MOD)+n)\mathcal{O}(MAXN * \log(MOD) + n)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const int MAXN = 1e6;
 
array<ll, MAXN + 1> fact;  // fact[i] = i! % MOD
array<ll, MAXN + 1> inv;   // inv[i] = inverso modular de fact[i];
 
// calcular a ^ b (mod m) en tiempo log b
ll modpow(ll a, ll b, ll m) {
	ll prod = 1;
	while (b > 0) {
		if (b % 2 == 1) { prod = (prod * a) % m; }
		b /= 2;
		a = (a * a) % m;
	}
	return prod;
}
 
int main() {
	// precomputar fact[i] e inv[i]
	fact[0] = inv[0] = fact[1] = inv[1] = 1;
	for (int i = 2; i <= MAXN; i++) {
		fact[i] = fact[i - 1] * i % MOD;
		inv[i] = modpow(fact[i], MOD - 2, MOD);
	}
 
	string s;
	cin >> s;
 
	vector<int> character_count(26);
	for (char i : s) { character_count[i - 'a']++; }
 
	ll total = fact[s.length()];
	for (int i : character_count) {
		// multiplicar por el inverso es lo mismo que dividir
		total = total * inv[i] % MOD;
	}
 
	cout << total << endl;
}
from collections import Counter
 
MAXN = 10**6
MOD = 10**9 + 7
 
fac = [0] * (MAXN + 1)
inv = [0] * (MAXN + 1)
 
 
# BeginCodeSnip{Combinatorics Functions (from the module)}
def exp(x: int, n: int, m: int) -> int:
	x %= m
	res = 1
	while n > 0:
		if n % 2 == 1:
			res = res * x % m
		x = x * x % m
		n //= 2
	return res
 
 
def factorial():
	fac[0] = 1
	for i in range(1, MAXN + 1):
		fac[i] = fac[i - 1] * i % MOD
 
 
def inverses():
	inv[MAXN] = exp(fac[MAXN], MOD - 2, MOD)
	for i in range(MAXN, 0, -1):
		inv[i - 1] = inv[i] * i % MOD
 
 
# EndCodeSnip
 
s = input()
character_count = Counter(s)
factorial()
inverses()
 
total = fac[len(s)]
for x in character_count.values():
	total = total * inv[x] % MOD
 
print(total)
Fundamentos