Skip to Content
CTRL K

Strivore

Pista 1

La respuesta no depende del contenido de SS.

Pista 2

Supongamos que fijamos las posiciones de los caracteres de SS relativas a los insertados. ¿Cómo podemos asignar valores a los caracteres insertados de modo que se evite el sobreconteo?

Solución

Análisis oficial 

Análisis alternativo 

La solución oficial dice que si no permitimos que los caracteres justo antes de un carácter de SS sean iguales a dicho carácter, igual podemos contar todas las cadenas posibles.

Aunque es un tanto poco intuitivo, otra forma de pensarlo es:

Para cualquier cadena posible, recorremos los caracteres y asignamos de forma voraz el primer carácter que coincide con el de SS. Está garantizado que cualquier carácter inmediatamente anterior a uno asignado no será igual al carácter asignado.

Una de las cadenas obtenibles a partir de la entrada de ejemplo 1 es moonwoff. Podemos tomar las dos primeras o y la penúltima f.

Tras esta intuición (esperemos que útil), sigue la implementación.

Implementación

Complejidad temporal: O(K+∣S∣)\mathcal{O}(K + |S|)

#include <iostream>
#include <string>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
constexpr int MOD = 1e9 + 7;
 
// https://usaco.guide/gold/modular?lang=cpp#solution---exponentiation
long long pow(long long base, long long exp) {
	base %= MOD;
	long long res = 1;
	while (exp > 0) {
		if (exp % 2 == 1) { res = res * base % MOD; }
		base = base * base % MOD;
		exp /= 2;
	}
	return res;
}
 
long long mod_inv(long long n) { return pow(n, MOD - 2); }
 
int main() {
	int char_num;
	std::string str;
	std::cin >> char_num >> str;
 
	// place_num[i] = (str.size() + i) choose str.size()
	vector<long long> place_num{1};
	for (int i = 1; i <= char_num; i++) {
		place_num.push_back(place_num.back() * (i + str.size() - 1) % MOD * mod_inv(i) %
		                    MOD);
	}
 
	long long total = 0;
	for (int back_num = 0; back_num <= char_num; back_num++) {
		// Cantidad de formas de colocar los caracteres de S
		long long str_amt = place_num[char_num - back_num];
		// Cantidad de formas de asignar caracteres sin violar la condición
		long long front_amt = pow(25, char_num - back_num);
		// Y por último, la cantidad de formas de hacer los caracteres de atrás
		long long back_amt = pow(26, back_num);
		total = (total + str_amt * front_amt % MOD * back_amt % MOD) % MOD;
	}
 
	cout << total << endl;
}
import java.io.*;
 
public class Main {
	private static final int MOD = (int)1e9 + 7;
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int charNum = Integer.parseInt(read.readLine());
		String str = read.readLine();
 
		// placeNum[i] = (str.length() + i) choose str.length()
		long[] placeNum = new long[charNum + 1];
		placeNum[0] = 1;
		for (int i = 1; i <= charNum; i++) {
			placeNum[i] =
			    (placeNum[i - 1] * (i + str.length() - 1) % MOD * modInv(i) % MOD);
		}
 
		long total = 0;
		for (int backNum = 0; backNum <= charNum; backNum++) {
			// Cantidad de formas de colocar los caracteres de S
			long strAmt = placeNum[charNum - backNum];
			// Cantidad de formas de asignar caracteres sin violar la condición
			long frontAmt = pow(25, charNum - backNum);
			// Y por último, la cantidad de formas de hacer los caracteres de atrás
			long backAmt = pow(26, backNum);
			total = (total + strAmt * frontAmt % MOD * backAmt % MOD) % MOD;
		}
 
		System.out.println(total);
	}
 
	static long modInv(long n) { return pow(n, MOD - 2); }
 
	// https://usaco.guide/gold/modular?lang=java#solution---exponentiation
	static long pow(long base, long exp) {
		base %= MOD;
		long res = 1;
		while (exp > 0) {
			if (exp % 2 == 1) { res = res * base % MOD; }
			base = base * base % MOD;
			exp /= 2;
		}
		return res;
	}
}
MOD = 10**9 + 7
 
 
def mod_inv(n: int):
	return pow(n, MOD - 2, MOD)
 
 
char_num = int(input())
str_ = input()
 
# place_num[i] = (len(str) + i) choose len(str)
place_num = [1]
for i in range(1, char_num + 1):
	place_num.append(place_num[-1] * (i + len(str_) - 1) * mod_inv(i) % MOD)
 
total = 0
for back_num in range(0, char_num + 1):
	# Cantidad de formas de colocar los caracteres de S
	str_amt = place_num[char_num - back_num]
	# Cantidad de formas de asignar caracteres sin violar la condición
	front_amt = pow(25, char_num - back_num, MOD)
	# Y por último, la cantidad de formas de hacer los caracteres de atrás
	back_amt = pow(26, back_num, MOD)
	total = (total + str_amt * front_amt * back_amt) % MOD
 
print(total)
Fundamentos