So I was solving this problem and I can’t seem to find my error. My solution seems to be the same idea as the one as the editorial. I downloaded the test data from the USACO website and couldn’t make any progress. I feel like it is a small error and I was hoping that you guys could tell me what it is.
Solution
#include <bits/stdc++.h>
using namespace std;
const int mxn=5e5+1,mod=1e9+7;
int n,m,k,dp[mxn],ans=1;
pair<int,int> info[mxn]; // keeps track of each cow's syllabes and rhyme class
map<string,int> scheme; // keeps track of how many times each rhyme comes up in the poem
map<int,vector<int>> type; // organizes each cow's syllables into a seperate rhyme class
map<int,int> vals; // number of ways for a line to end with a specific rhyme class
int main(){
cin.tie(0)->sync_with_stdio(0);
freopen("poetry.in", "r", stdin);
freopen("poetry.out", "w",stdout);
cin >> n >> m >> k;
for(int i=1;i<=n;i++){
cin >> info[i].first >> info[i].second;
type[info[i].second].push_back(info[i].first); // putting each cow's syllables in it's rhyme class
}
for(int i=1;i<=m;i++){
string a;cin >> a;
scheme[a]++; // adding the number of time a rhyme needs to occur
}
dp[0]=1;
for(int i=0;i<=k;i++)
for(int j=1;j<=n;j++)
if(info[j].first<=i)
dp[i]+=dp[i-info[j].first],dp[i]%=mod; // number of ways to have lines of length i (order matters)
for(auto i:type)
for(auto j:i.second)
vals[i.first]+=dp[k-j],vals[i.first]%=mod; // number of lines that end with the same ryhme class
for(auto s:scheme){
int num=0;
for(auto i:vals)
num+=pow(i.second,s.second);
ans*=num;
ans%=mod;
}
cout << ans; // basically what the editorial says
}
Thanks!!