Official Analysis (C++ and Java)

Explanation

Observe that the order of the words beside the last word in each line is independent from the order of the lines. Because of this, we can separate this problem into two parts:

1. Calculate $f(i)$, which we'll define as the number of ways selected words can be arranged in a line that ends with a certain rhyme class $c_i$
2. Get the actual answer by figuring out different ways to map rhyme class $c$ to rhyme scheme $e$

Let's go through these steps with the sample test case: here it is again for reference.

3 3 10
3 1
4 1
3 2
A
B
A

There are $8$ different ways to arrange the words such that a line ends with a word with rhyme class $1$, and $4$ ways for rhyme class $2$, so $f(1) = 8$ and $f(2) = 4$.

We can map the rhyme class to scheme in four different ways, so we have $f(1)^3 + f(1)^2f(2) + f(2)^2f(1) + f(2)^3 = 960$.

Let's work through these parts in order.

Part 1

This part is a bit similar to the knapsack problem. We're given a total length $k$ along with some words of syllable length $s_i$, and we need find the total number of ways to arrange a subset of the words such that the total is $k$ syllables.

Let $dp[i]$ be the number of ways to satisfy a total length $i$, and $p[j]$ be the number of words with $j$ syllables. Our transition is as follows:

Now it remains to define our $f(i)$. $dp[k]$ tells us the number of ways to fits words under length $k$, but it doesn't specify what the ending word's rhyme class is. To do that, we use a summation as follows for our definition:

Part 2

Notice that given any rhyme scheme, the final answer they produce is equivalent to if any two lines of the scheme is switched. This is true because the combinations that one line can have doesn't affect any other line.

So, to make our calculations easier, we can sort the rhyme scheme, count the number of lines that have the same type, and put them in a set (let's call that set $q$). In our example, $q = [2, 1]$.

To calculate our final answer, we just need to find the sum of this polynomial below. To keep it simple, let's just assume total number of rhyme classes is $2$.

But this polynomial is pretty darn awful, and the number of terms in it grows much faster than the number of rhyme classes.

To solve this, we have to notice that this polynomial is actually symmetrical, and we can instead express the expression as products of power series:

When we expand this, we get the exact same distribution of the powers in the polynomial above.

Implementation

Time Complexity: $\mathcal{O}(NK+(N+M)\log M)$

Copy
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const ll MOD = 1e9 + 7;

 Code Snippet: Modular exponentiation (from the module) (Click to expand)

int main() {
	ifstream fin("poetry.in");

Copy
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();

Copy
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