Skip to content

Instantly share code, notes, and snippets.

@rendon
Created June 4, 2014 04:48
Show Gist options
  • Save rendon/b12375831e143732cb63 to your computer and use it in GitHub Desktop.
Save rendon/b12375831e143732cb63 to your computer and use it in GitHub Desktop.
Codeforces #248 Div 2 E. Tachibana Kanade's Tofu
//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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment