CF1728G Illumination

考虑坐标轴上的一段区间 $[0, d]$。在该区间内有 $n$ 个灯笼和 $m$ 个兴趣点。 对于每个灯笼，你可以为其选择一个功率——一个在 $0$ 到 $d$ 之间（包含 $0$ 和 $d$）的整数。坐标为 $x$ 的灯笼可以照亮坐标为 $y$ 的兴趣点，当且仅当 $|x - y|$ 小于等于该灯笼的功率。 如果所有兴趣点都被至少一个灯笼照亮，则称为所有灯笼分配功率的一种方案是合法的。 你需要处理 $q$ 个询问。每个询问由一个整数 $f_i$ 表示。对于第 $i$ 个询问，你需要： - 在坐标 $f_i$ 处添加一个灯笼； - 计算所有灯笼分配功率的合法方案数，并输出其对 $998244353$ 取模的结果； - 移除刚刚添加的灯笼。

第一行包含三个整数 $d$、$n$ 和 $m$（$4 \le d \le 3 \cdot 10^5$；$1 \le n \le 2 \cdot 10^5$；$1 \le m \le 16$），分别表示区间的长度、灯笼的数量和兴趣点的数量。 第二行包含 $n$ 个整数 $l_1, l_2, \dots, l_n$（$1 \le l_i \le d - 1$），其中 $l_i$ 表示第 $i$ 个灯笼的坐标。 第三行包含 $m$ 个整数 $p_1, p_2, \dots, p_m$（$1 \le p_i \le d - 1$），其中 $p_i$ 表示第 $i$ 个兴趣点的坐标。 第四行包含一个整数 $q$（$1 \le q \le 5 \cdot 10^5$），表示询问的数量。 第五行包含 $q$ 个整数 $f_1, f_2, \dots, f_q$（$1 \le f_i \le d - 1$），其中 $f_i$ 表示第 $i$ 个询问对应的灯笼坐标。 输入的额外限制：在处理每个询问的过程中，任何坐标上都不会有多个物体（即不会有两个或以上的灯笼在同一坐标、两个或以上的兴趣点在同一坐标，或者某个坐标同时有灯笼和兴趣点）。

对于每个询问，输出一个整数，表示答案对 $998244353$ 取模的结果。

由 ChatGPT 4.1 翻译