Cow Poetry

Explicación

Observemos que el orden de las palabras aparte de la última palabra de cada verso es independiente del orden de los versos. Por esto, podemos separar este problema en dos partes:

Calcular $f(i)$ , que definiremos como el número de formas en que las palabras seleccionadas se pueden disponer en un verso que termina con una cierta clase de rima $c_i$
Obtener la respuesta real hallando distintas formas de mapear la clase de rima $c$ al esquema de rima $e$

Recorramos estos pasos con el caso de prueba de ejemplo: aquí está de nuevo como referencia.

Hay $8$ formas distintas de disponer las palabras de modo que un verso termine con una palabra de clase de rima $1$ , y $4$ formas para la clase de rima $2$ , así que $f(1) = 8$ y $f(2) = 4$ .

Podemos mapear la clase de rima al esquema de cuatro formas distintas, así que tenemos $f(1)^3 + f(1)^2f(2) + f(2)^2f(1) + f(2)^3 = 960$ .

Trabajemos estas partes en orden.

Parte 1

Esta parte es un poco similar al problema de la mochila (knapsack). Se nos da una longitud total $k$ junto con algunas palabras de longitud en sílabas $s_i$ , y necesitamos hallar el número total de formas de disponer un subconjunto de las palabras de modo que el total sea $k$ sílabas.

Sea $dp[i]$ el número de formas de satisfacer una longitud total $i$ , y $p[j]$ el número de palabras con $j$ sílabas. Nuestra transición es la siguiente:

dp[i] = \sum_{j=0}^{i} dp[i-j] \cdot p[j]

Ahora resta definir nuestro $f(i)$ . $dp[k]$ nos dice el número de formas de encajar palabras bajo longitud $k$ , pero no especifica cuál es la clase de rima de la palabra final. Para eso, usamos una sumatoria de la siguiente forma para nuestra definición:

f(i) = \sum_{j=0}^{k} dp[k-j] \cdot p_i[j]

Parte 2

Nótese que, dado cualquier esquema de rima, la respuesta final que producen es equivalente si se intercambian cualesquiera dos versos del esquema. Esto es cierto porque las combinaciones que puede tener un verso no afectan a ningún otro verso.

Así, para facilitar nuestros cálculos, podemos ordenar el esquema de rima, contar el número de versos que tienen el mismo tipo, y ponerlos en un conjunto (llamemos a ese conjunto $q$ ). En nuestro ejemplo, $q = [2, 1]$ .

Para calcular nuestra respuesta final, solo necesitamos hallar la suma de este polinomio de abajo. Para mantenerlo simple, asumamos que el número total de clases de rima es $2$ .

f(1)^{p_1+ \dots +p_k} + f(1)^{p_1 + \dots + p_{k-1}} f(2)^{p_k} + \dots + f(1)^{p_1} f(2)^{p_2 + \dots + p_k} + f(2)^{p_1+ \dots + p_k}

Pero este polinomio es bastante horrible, y el número de términos crece mucho más rápido que el número de clases de rima.

Para resolver esto, tenemos que notar que este polinomio es en realidad simétrico, y en cambio podemos expresar la expresión como productos de series de potencias:

(f(1)^{p_1} + f(2)^{p_1})(f(1)^{p_2} + f(2)^{p_2}) \cdots (f(1)^{p_k} + f(2)^{p_k})

Cuando expandimos esto, obtenemos exactamente la misma distribución de las potencias en el polinomio de arriba.

Implementación

Complejidad temporal: $\mathcal{O}(NK+(N+M)\log M)$

C++JavaPython


#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
const ll MOD = 1e9 + 7;
 
// BeginCodeSnip{Modular exponentiation (from the module)}
ll mod_exp(ll a, ll b) {
	if (a == 0) { return 0; }
	ll ret = 1;
	while (b > 0) {
		if (b % 2 == 1) { ret = (ret * a) % MOD; }
		a = (a * a) % MOD;
		b /= 2;
	}
	return ret;
}
// EndCodeSnip
 
int main() {
	ifstream fin("poetry.in");
	ofstream fout("poetry.out");
 
	int n, m, k;
	fin >> n >> m >> k;
	// Keep track of how many words have the same # of syllables
	// and how many words are in the same rhyme class
	vector<ll> count(k + 1, 0);
	vector<vector<ll>> type(n + 1);
	for (int i = 0; i < n; i++) {
		int a, b;
		fin >> a >> b;
		count[a]++;
		type[b].push_back(a);
	}
	vector<int> rhyme(m);
	for (int i = 0; i < m; i++) {
		char a;
		fin >> a;
		rhyme[i] = int(a - 'A');
	}
 
	// First part
	vector<ll> dp(k + 1, 0);
	dp[0] = 1;
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j <= i; j++) { dp[i] = (dp[i] + (dp[i - j] * count[j])) % MOD; }
	}
	vector<ll> total(n + 1, 0);
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < type[i].size(); j++) {
			total[i] = (total[i] + dp[k - type[i][j]]) % MOD;
		}
	}
	if (dp[k] == 0) {
		fout << 0;
		return 0;
	}
 
	// Second part
	sort(rhyme.begin(), rhyme.end());
	vector<int> groups;
	rhyme.push_back(-1);
	int back = 0;
	for (int i = 1; i <= m; i++) {
		if (rhyme[i] != rhyme[i - 1]) {
			groups.push_back(i - back);
			back = i;
		}
	}
 
	ll ans = 1;
	for (int i = 0; i < groups.size(); i++) {
		ll curr = 0;
		for (int j = 1; j <= n; j++) {
			curr = (curr + mod_exp(total[j], groups[i])) % MOD;
		}
		ans = (ans * curr) % MOD;
	}
 
	fout << ans << endl;
}


import java.io.*;
import java.util.*;
 
public class CowPoetry {
	private final static int MOD = 1000000007;
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("poetry");
 
		int n = io.nextInt();
		int m = io.nextInt();
		int k = io.nextInt();
 
		long[] count = new long[k + 1];
		List<Integer>[] type = new ArrayList[n + 1];
 
		for (int i = 0; i <= n; i++) { type[i] = new ArrayList<Integer>(); }
 
		for (int i = 0; i < n; i++) {
			int a = io.nextInt();
			int b = io.nextInt();
			count[a]++;
			type[b].add(a);
		}
 
		int[] rhyme = new int[m];
		for (int i = 0; i < m; i++) {
			char a = io.next().charAt(0);
			rhyme[i] = (a - 'A');
		}
 
		long[] dp = new long[k + 1];
		dp[0] = 1;
		for (int i = 1; i <= k; i++) {
			for (int j = 0; j <= i; j++) {
				dp[i] = (dp[i] + (dp[i - j] * count[j])) % MOD;
			}
		}
 
		long[] total = new long[n + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < type[i].size(); j++) {
				total[i] = (total[i] + dp[k - type[i].get(j)]) % MOD;
			}
		}
 
		if (dp[k] == 0) {
			io.println(0);
			io.close();
			return;
		}
 
		Arrays.sort(rhyme);
		List<Integer> groups = new ArrayList<>();
		int back = 0;
		for (int i = 1; i <= m; i++) {
			if (i == m || rhyme[i] != rhyme[i - 1]) {
				groups.add(i - back);
				back = i;
			}
		}
 
		long ans = 1;
		for (int i = 0; i < groups.size(); i++) {
			long curr = 0;
			for (int j = 1; j <= n; j++) {
				curr = (curr + exp(total[j], groups.get(i))) % MOD;
			}
			ans = (ans * curr) % MOD;
		}
 
		io.println(ans);
		io.close();
	}
 
	// BeginCodeSnip{Modular exponentiation (from the module)}
	private static long exp(long x, long n) {
		assert (n >= 0);
		x %= MOD;
		long res = 1;
		while (n > 0) {
			if (n % 2 == 1) { res = res * x % MOD; }
			x = x * x % MOD;
			n /= 2;
		}
		return res;
	}
 
	// EndCodeSnip
 
	// CodeSnip{Kattio}
}


MOD = 1000000007
 
with open("poetry.in") as read:
	n, m, k = map(int, read.readline().split())
	count = [0] * (k + 1)
	type = [[] for _ in range(n + 1)]
 
	for i in range(n):
		a, b = map(int, read.readline().split())
		count[a] += 1
		type[b].append(a)
 
	rhyme = []
	for i in range(m):
		a = read.readline().strip()
		rhyme.append(ord(a) - ord("A"))
 
 
dp = [0] * (k + 1)
dp[0] = 1
 
lengths = [i for i in range(1, k + 1) if count[i] > 0]
 
for i in range(1, k + 1):
	for j in lengths:
		if j <= i:
			dp[i] = (dp[i] + (dp[i - j] * count[j])) % MOD
 
 
total = [0] * (n + 1)
for i in range(1, n + 1):
	for j in range(len(type[i])):
		total[i] = (total[i] + dp[k - type[i][j]]) % MOD
 
if dp[k] == 0:
	print(0, file=open("poetry.out", "w"))
	exit(0)
 
rhyme.sort()
groups = []
rhyme.append(-1)
back = 0
 
for i in range(1, m + 1):
	if rhyme[i] != rhyme[i - 1]:
		groups.append(i - back)
		back = i
 
ans = 1
for i in range(len(groups)):
	curr = 0
	for j in range(1, n + 1):
		curr = curr + pow(total[j], groups[i], MOD)
	ans = (ans * curr) % MOD
 
print(ans, file=open("poetry.out", "w"))