Cow Poetry

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.

#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(){
    freopen("", "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
    for(int i=0;i<=k;i++)
        for(int j=1;j<=n;j++)
                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)
    cout << ans; // basically what the editorial says


Maybe try storing your data in long longs instead?

No, that isn’t it

Oh wait, I think integer overflow might be occurring when you’re calling pow.

ok I’ll make a binpow function then

So some of the test cases are correct now, I think I can solve the rest of them by myself. Thanks so much!

1 Like

Yea it mostly because if integer overflow