#6517. 「雅礼集训 2018 Day11」字符串

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

N 个字符串,每个字符串有一个权值 v_i 。随后给出 M 次询问,每次对一个区间进行检测。令最长的字符串长度为 L ,那么会给出 g_1, ..., g_L 表示每个长度的字符串的「识别值」。

对若干个字符串构成的集合 P 进行测试的过程如下:

对字符串 S 定义 f(S) 表示 S P 中以其为前缀出现的串的权值和。 那么如果 S P 中作为前缀出现过,并且 Bf(S) + A\times {\rm len}(S) \geq C ,那么则将 g_{{\rm len}(S)} 加入集合 G

最后随机选择一个区间 [x, y](1 \leq x \leq y \leq L) ,如果 [x, y] \bigcap G \neq \emptyset ,那么测试成功,否则测试失败。输出测试成功的概率并用最简分数表示。

特别地,整数 k 表示为 k / 1

输入格式

第一行四个数 N, A, B, C

接下来一行 N 个数 v_1, ..., v_N

接下来 N 行表示 N 个字符串。

接下来一行 L 个数表示 g_{1}, ... ,g_L ,保证 g_1, ..., g_L 是一个 1 L 的排列。

接下来一行一个数 M

接下来 M 行,每行两个数 l, r ,表示对第 l 到第 r 个字符串进行测试。

输出格式

M 个数表示答案。

样例

样例输入 1

5 2 3 15
1 2 3 2 0
aba
aa
abb
aaa
bbbb
1 3 2 4
6
1 4
1 3
2 3
2 4
5 5
3 5

样例输出 1

9/10
9/10
7/10
9/10
0/1
7/10

数据范围与提示

测试点编号 N, M \leq \sum\left\vert s_i\right\vert \leq s_i \leq
1 10 30
2 100 300
3 1000 3000
4 10000 30000 10
5 10^5 3\times 10^5
6 10000 30000
7 20000 50000
8 30000 70000
9 50000 100000
10 10^5 3\times 10^5

对于 100 \% 的数据, 0 \leq v_i, A, B, C \leq 10^9