In order to solve this problem, we must make a series of observations. The first is that it doesn’t matter what order the rhyme classes are given - what matters is the frequencies of each rhyme class. Once we compute the frequency of each rhyme class $f_i$ and the number of ways to end a line with a rhyme $w_k,$ the number of poems that bessie can write for that rhyme class is
For instance, there are $8$ ways to end in rhyme $1$ and $4$ ways to end in rhyme $2$. There are $2$ of rhyme class $A$ and $1$ of rhyme class $B$. Thus, the answer is
Now, we need to find the number of ways to form a line that ends in each rhyme. To do this, we use dynamic programming. Let $dp[i]$ be the number of ways to form a line of length $i.$ The transition between states is, for the number of syllables in every word $w_s,$ is:
(Don’t forget to modulo 1,000,000,007 at every step!)
Whenever $w_s + i == K,$ we increment $r[w_r],$ where $w_r$ is the rhyme of that word and $r$ is an array storing the number of ways to form a line that ends in each rhyme.
Finally, to implement the math formula that we discussed in the first paragraph, we need to use an efficient exponentiation algorithm, which can compute $E^{P} \mod 1000000007$ in $O(\log{P}).$ Using std::pow() or Math.pow() will not work because of the possibility of large numbers.
The efficiency of the dynamic programming is $O(NK)$ and the exponentiation is $O(NM\log{M} )$ for the worst case, which fits inside the time limit.
#include <bits/stdc++.h>
#define MAXN 5005
#define MAXM 100005
#define MAXS 5005
using namespace std;
long long MOD = 1000000007;
//fast exponentiation
long long exp(int base, int power){
if(power == 0) return 1;
if(power == 1) return (base + MOD) % MOD;
long long ans = exp(base,power/2);
ans = (ans * ans + MOD) % MOD;
if(power%2 == 1) ans = (ans*base + MOD) % MOD;
return (ans + MOD) % MOD;
}
int n,m,s;
long long dp[MAXS];
//dp[x] = the number of ways to make a line with x syllables.
long long r[MAXN];
//r[x] = the number of ways to form a full line that ends with rhyme scheme x
unordered_map<char,int> umap;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
ifstream fin ("poetry.in");
ofstream fout ("poetry.out");
int n,m,s;
fin >> n >> m >> s;
pair<int,int> words[n]; //first is syllables, second is rhyme
for(int k = 0; k < n; k++){
int a,b;
fin >> a >> b;
words[k] = make_pair(a,b);
}
//Calculate frequencies of every rhyme (Order of rhymes doesn't matter)
for(int k = 0; k < m; k++){
char c;
fin >> c;
if(umap.find(c) == umap.end()){
umap[c] = 1;
} else{
umap[c]++;
}
}
dp[0] = 1;
for(int k = 0; k <= s; k++){
for(int j = 0; j < n; j++){
if(words[j].first + k > s) continue;
if(words[j].first + k == s){
r[words[j].second] = (r[words[j].second] + dp[k] + MOD) % MOD; //if you are at the end of the line, update r
} else {
dp[words[j].first + k] = (dp[words[j].first + k] + dp[k] + MOD) % MOD; //knapsack dp
}
}
}
long long answer = 1;
for(auto a : umap){
//use counting/probability to calculate the answer.
//For every grouping of a rhyme, multiply the answer by
//r[1]^freq, r[2]^freq, etc.
//For instance, the answer for the sample case is
//(8^2 + 4^2) * (8^1 + 4^1). r[1] = 8 and r[2] = 4, and the are 2 As and 1 B.
int freq = a.second;
long long sum = 0;
for(int k = 0; k <= n; k++){
if(r[k] == 0) continue;
sum = (sum + exp(r[k],freq) + MOD) % MOD;
}
answer = (answer * sum + MOD) % MOD;
}
cout << answer;
fout << answer;
return 0;
}
Here is the same solution but in Java:
import java.io.*;
import java.util.*;
class poetry{
public static long MOD = 1000000007L;
public static void main(String[] args) throws IOException{
BufferedReader f = new BufferedReader(new FileReader("poetry.in"));
PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("poetry.out")));
StringTokenizer st = new StringTokenizer(f.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
Word[] words = new Word[n];
for(int k = 0; k < n; k++){
st = new StringTokenizer(f.readLine());
int sy = Integer.parseInt(st.nextToken());
int rh = Integer.parseInt(st.nextToken());
words[k] = new Word(sy,rh);
}
//Calculate frequencies of every rhyme (Order of rhymes doesn't matter)
HashMap<Character,Integer> hmap = new HashMap<Character,Integer>();
for(int k = 0; k < m; k++){
char c = f.readLine().charAt(0);
if(hmap.containsKey(c)){
hmap.put(c,hmap.get(c)+1);
} else {
hmap.put(c,1);
}
}
//dp[x] = the number of ways to make a line with x syllables.
long[] dp = new long[s+1];
dp[0] = 1L;
//r[x] = the number of ways to form a full line that ends with rhyme scheme x
long[] r = new long[n+1];
for(int k = 0; k <= s; k++){
for(int j = 0; j < n; j++){
if(words[j].s + k > s) continue;
if(words[j].s + k == s){
r[words[j].r] = (r[words[j].r] + dp[k] + MOD) % MOD; //if you are at the end of the line, update r
}
dp[words[j].s + k] = (dp[words[j].s + k] + dp[k] + MOD) % MOD; //knapsack dp
}
}
long answer = 1L;
for(char c : hmap.keySet()){
//use counting/probability to calculate the answer. For every grouping of a rhyme, multiple the answer by r[1]^freq, r[2]^freq, etc.
//For instance, the answer for the sample case is (8^2 + 4^2) * (8^1 + 4^1). r[1] = 8 and r[2] = 4, and the are 2 As and 1 B.
int freq = hmap.get(c);
long sum = 0L;
for(int k = 0; k < r.length; k++){
if(r[k] == 0) continue;
sum = (sum + exp(r[k],freq) + MOD) % MOD;
}
answer = (answer * sum + MOD) % MOD;
}
System.out.println(answer);
out.println(answer);
out.close();
}
//fast exponentiation
public static long exp(long base, int power){
if(power == 0) return 1;
if(power == 1) return (base + MOD) % MOD;
long ans = exp(base,power/2);
ans = (ans*ans + MOD) % MOD;
if(power%2 == 1) ans = (ans*base + MOD) % MOD;
return (ans + MOD) % MOD;
}
public static class Word{
int s; //syllables
int r; //rhyme
public Word(int a, int b){
s = a;
r = b;
}
}
}