Codeforces #248 Div 2 E. Tachibana Kanade's Tofu

tachibana_kanades_tofu.cpp

//region Template
#include <bits/stdc++.h>
//#define ONLINE_JUDGE
using namespace std;
//ios_base::sync_with_stdio(false);
inline int log(const char* format, ...)
{
#ifndef ONLINE_JUDGE
    va_list args;
    va_start(args, format);
    int code = vfprintf(stderr, format, args);
    va_end(args);
    return code;
#else
    return 0;
#endif
}

const double EPS    = 10e-8;
const int MAX       = 201;
const int INF       = 1 << 30;
const int MOD = 1000000007ll;
//endregion

vector<int> l;
vector<int> r;
vector<int> numbers[MAX];
int V[MAX];
int g[MAX][20];
int f[MAX];
int output[MAX];
int new_state = 1;
int dp[MAX][501][MAX][2][2];
int m;

void enter(const vector<int> &number, int value)
{
    int state = 0;
    unsigned j;
    for (j = 0; j < number.size(); j++) {
        if (g[state][number[j]] == -1)
            break;
        state = g[state][number[j]];
    }

    for ( ; j < number.size(); j++) {
        g[state][number[j]] = new_state++;
        state = g[state][number[j]];
    }

    output[state] += value;
}

/**
 @param gt greater than, true if the digit in the current position can be
 greater than the digit at the same position of the original number, this is
 to ensure tha we never exceed the upper bound (num).

 @param lz leading zero, true if the current position is a leading zero.
*/
int solve(int pos, int sum, int state, bool gt, bool lz, vector<int> &num)
{
    if (pos == int(num.size())) {
        if (lz)  return 0;
        else    return sum > 0;
    } else {
        int &ans = dp[pos][sum][state][gt][lz];
        if (ans != -1)
            return ans;

        ans = 0;
        int max_digit = gt ? m - 1 : num[pos];
        for (int d = 0; d <= max_digit; d++) {
            lz &= (d == 0);
            int s = state;
            if (!lz) {
                while (g[s][d] == -1)
                    s = f[s];
                s = g[s][d];
            }
            bool g = gt || (d < max_digit);
            int new_sum = max(0, sum - output[s]);
            ans = (ans + solve(pos + 1, new_sum, s, g, lz, num)) % MOD;
        }
        return ans;
    }
}

int main(int argc, char **argv)
{
    int n, k, len, num;
    scanf("%d %d %d", &n, &m, &k);
    scanf("%d", &len);
    for (int i = 0; i < len; i++) {
        scanf("%d", &num);
        l.push_back(num);
    }

    // Decrease by 1
    int borrow = 1;
    for (int j = l.size() - 1; j >= 0; j--) {
        int d = l[j] - borrow;
        borrow = 0;
        if (d < 0) {
            d += m;
            borrow = 1;
        }

        l[j] = d;
    }

    if (l[0] == 0)
        l.erase(l.begin());


    scanf("%d", &len);
    for (int i = 0; i < len; i++) {
        scanf("%d", &num);
        r.push_back(num);
    }

    for (int i = 0; i < n; i++) {
        scanf("%d", &len);
        for (int j = 0; j < len; j++) {
            scanf("%d", &num);
            numbers[i].push_back(num);
        }

        scanf("%d", &V[i]);
    }

    // Build Aho-Corasick Automata
    memset(g, -1, sizeof g);
    memset(f, -1, sizeof f);
    memset(output, 0, sizeof output);

    // Build goto function
    for (int i = 0; i < n; i++)
        enter(numbers[i], V[i]);

    for (int a = 0; a < m; a++) {
        if (g[0][a] == -1)
            g[0][a] = 0;
    }


    // Build fail function
    queue<int> Q;
    for (int a = 0; a < m; a++) {
        int s = g[0][a];
        if (s != 0) {
            Q.push(s);
            f[s] = 0;
        }
    }

    while (!Q.empty()) {
        int r = Q.front();
        Q.pop();
        for (int a = 0; a < m; a++) {
            int s = g[r][a];
            if (s != -1) {
                Q.push(s);
                int state = f[r];
                while (g[state][a] == -1)
                    state = f[state];
                f[s] = g[state][a];
                output[s] += output[f[s]];
            }
        }
    }


    // The value that we are looking for is f(r) - f(l - 1)
    memset(dp, -1, sizeof dp);
    int high = solve(0, k + 1, 0, false, true, r);

    memset(dp, -1, sizeof dp);
    int low = solve(0, k + 1, 0, false, true, l);

    int ans = (high - low + MOD) % MOD;

    printf("%d", ans);
    return EXIT_SUCCESS;
}