A6654. 「雅礼集训 2018 Day11」字符串
编程题
提高+/省选-
知识点
题目描述
有 $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$。
对若干个字符串构成的集合 $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$ 个字符串进行测试。
接下来一行 $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$ | $10$ |
| 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$。
| :-: | :-: | :-: | :-: |
| 1 | $10$ | $30$ | |
| 2 | $100$ | $300$ | |
| 3 | $1000$ | $3000$ | |
| 4 | $10000$ | $30000$ | $10$ |
| 5 | $10^5$ | $3\times 10^5$ | $10$ |
| 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$。