Tachibana Kanade's Toku(AC自动机+数位DP)

描述

传送门:Codeforces Round #248 (Div. 1) - Problem C

Tachibana Kanade likes Mapo Tofu very much. One day, the canteen cooked all kinds of tofu to sell, but not all tofu is Mapo Tofu, only those spicy enough can be called Mapo Tofu.

Each piece of tofu in the canteen is given a m-based number, all numbers are in the range $[l, r]$ ($l$ and $r$ being m-based numbers), and for every m-based integer in the range $[l, r]$, there exists a piece of tofu with that number.

To judge what tofu is Mapo Tofu, Tachibana Kanade chose n m-based number strings, and assigned a value to each string. If a string appears in the number of a tofu, the value of the string will be added to the value of that tofu. If a string appears multiple times, then the value is also added that many times. Initially the value of each tofu is zero.

Tachibana Kanade considers tofu with values no more than k to be Mapo Tofu. So now Tachibana Kanade wants to know, how many pieces of tofu are Mapo Tofu?

Input

The first line contains three integers $n$, $m$ and $k$ ($1 ≤ n ≤ 200$; $2 ≤ m ≤ 20$; $1 ≤ k ≤ 500$). Where $n$ denotes the number of strings, $m$ denotes the base used, and $k$ denotes the limit of the value for Mapo Tofu.

The second line represents the number $l$. The first integer in the line is $len$ ($1 ≤ len ≤ 200$), describing the length (number of digits in base $m$) of $l$. Then follow len integers $a_1, a_2, …, a_{len}$ ($0 ≤ a_i < m$; $a_1 > 0$) separated by spaces, representing the digits of $l$, with $a_1$ being the highest digit and alen being the lowest digit.

The third line represents the number $r$ in the same format as $l$. It is guaranteed that $1 ≤ l ≤ r$.

Then follow $n$ lines, each line describing a number string. The $i$-th line contains the $i$-th number string and $v_i$ — the value of the $i$-th string ($1 ≤ v_i ≤ 200$). All number strings are described in almost the same format as $l$, the only difference is number strings may contain necessary leading zeros (see the first example). The sum of the lengths of all number strings does not exceed $200$.

Output

Output the number of pieces of Mapo Tofu modulo $1000000007$ ($10^9 + 7$). The answer should be a decimal integer.

Examples

Input Output
1
2
3
4
5
2 10 1
1 1
3 1 0 0
1 1 1
1 0 1
1
97
1
2
3
4
5
2 10 12
2 5 9
6 6 3 5 4 9 7
2 0 6 1
3 6 7 2 1
1
635439
1
2
3
4
5
6
7
4 2 6
6 1 0 1 1 1 0
6 1 1 0 1 0 0
1 1 2
3 0 1 0 5
4 0 1 1 0 4
3 1 0 1 2
1
2

Note

In the first sample, $10$, $11$ and $100$ are the only three decimal numbers in $[1, 100]$ with a value greater than $1$. Here the value of $1$ is $1$ but not $2$, since numbers cannot contain leading zeros and thus cannot be written as “01”.

In the second sample, no numbers in the given interval have a value greater than $12$.

In the third sample, $110000$ and $110001$ are the only two binary numbers in the given interval with a value no greater than $6$.

思路

  • 把要匹配的串建一个AC自动机,处理出每个点的价值。
  • 然后数位DP即可。$dp[pos][state][sum]$即前$pos$位,在自动机上的状态为$state$,和为$sum$的满足条件的个数。
  • 但是统计$[l, r]$,我们一般会统计$[1, l - 1]$和$[1, r]$的,减一下。但是这里要得到$l - 1$就要手写一个减法,比较麻烦。
  • 于是学习了一波直接根据上下限DP的写法。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
using namespace std;

const int N = 1 << 8;
const int mod = 1e9 + 7;

struct Trie
{
int ch[N][20], f[N], val[N];
int sz, rt;
int newnode()
{
memset(ch[sz], -1, sizeof(ch[sz])), val[sz] = 0;
return sz++;
}
void insert(const vector<int>& s, int v)
{
int u = rt;
for (auto& c : s)
{
if (!~ch[u][c]) ch[u][c] = newnode();
u = ch[u][c];
}
val[u] += v;
}
void build()
{
queue<int> q;
f[rt] = rt;
for (int c = 0; c < m; c++)
{
if (~ch[rt][c])
f[ch[rt][c]] = rt, q.push(ch[rt][c]);
else
ch[rt][c] = rt;
}
while (!q.empty())
{
int u = q.front();
q.pop();
val[u] += val[f[u]];
for (int c = 0; c < m; c++)
{
if (~ch[u][c])
f[ch[u][c]] = ch[f[u]][c], q.push(ch[u][c]);
else
ch[u][c] = ch[f[u]][c];
}
}
}
vector<int> l, r;
int m, k;
int dp[N][N][N << 1];
void init(int m, int k)
{
sz = 0, rt = newnode();
this->m = m, this->k = k;
memset(dp, -1, sizeof(dp));
set(l), set(r);
assert(l.size() <= r.size());
l.resize(r.size());
}
void set(vector<int>& num)
{
int n;
scanf("%d", &n);
num.resize(n);
for (auto& t : num) scanf("%d", &t);
reverse(num.begin(), num.end());
}
int solve()
{
return dfs(r.size() - 1, rt);
}
int dfs(int pos, int state, int sum = 0, bool lead = true, bool limit_l = true, bool limit_r = true)
{
if (sum > k) return 0;
if (!~pos) return 1;
if (!limit_l && !limit_r && !lead && ~dp[pos][state][sum]) return dp[pos][state][sum];
int ans = 0;
for (int c = 0; c < m; c++)
{
if (limit_l && c < l[pos]) continue;
if (limit_r && c > r[pos]) continue;
int new_state = state;
if (!lead || c) new_state = ch[state][c];
ans += dfs(pos - 1, new_state, sum + val[new_state], lead && c == 0, limit_l && c == l[pos], limit_r && c == r[pos]);
if (ans >= mod) ans -= mod;
}
if (!limit_l && !limit_r && !lead) dp[pos][state][sum] = ans;
return ans;
}
} solver;

int main()
{
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
solver.init(m, k);
for (int i = 0, len, val; i < n; i++)
{
scanf("%d", &len);
vector<int> num(len);
for (auto& t : num) scanf("%d", &t);
scanf("%d", &val);
solver.insert(num, val);
}
solver.build();
printf("%d\n", solver.solve());
}
捐助作者
0%