P15601 [ICPC 2020 Jakarta R] Robust Defense

美国国防部（DoD）开发了一种据称无法被穿透的新型无线技术。这项新技术包含两种设备：发射器和接收器。尽管国防部试图使这些设备坚固耐用，但新型发射器可能会因某些原因损坏。另一方面，新型接收器相当坚固，设计为无法关闭。接收器是 **在线** 的当且仅当满足以下条件之一： - 存在两个活跃的（未损坏的）发射器，使得接收器恰好位于连接这两个发射器的线段上。 - 存在三个活跃的（未损坏的）发射器，使得接收器严格位于由这三个发射器构成的三角形内部。 这项新技术使国防部能够战略性地布置通信塔，从而使外部无法窃听其军事基地。有 $N$ 个军事基地，每个位于坐标 $(x_i, y_i)$ 处，以及 $M$ 个通信塔，每个位于坐标 $(x_j, y_j)$ 处。每个军事基地配备有新型接收器，每个通信塔配备有新型发射器。保证没有两个建筑（即军事基地或通信塔）位于同一位置。同时保证每个军事基地中的接收器都是在线状态，因此所有军事基地都处于在线状态。 一天，国防部预测一场强烈风暴将接近其通信塔。在这场强风暴期间，每个发射器有 $(100 - S)\%$ 的概率损坏，有 $S\%$ 的概率幸存（即未损坏）。 国防部请求你的帮助，计算在强风暴过后 **所有** 军事基地仍保持在线状态的概率。该概率可以表示为有理数 $\frac{P}{Q}$，其中 $P$ 和 $Q$ 是互质的整数。你需要输出一个整数 $P \cdot Q^{-1} \pmod{998\,244\,353}$，这里 $Q^{-1}$ 是 $Q$ 模 $998\,244\,353$ 的乘法逆元。换言之，你需要输出一个整数 $R$（$0 \leq R < 998\,244\,353$），使得 $P \equiv Q \cdot R \pmod{998\,244\,353}$。

输入第一行包含三个整数 $N$、$M$ 和 $S$（$1 \leq N \leq 500$；$2 \leq M \leq 500$；$0 < S < 100$），分别表示军事基地的数量、通信塔的数量以及发射器在强风暴中幸存（即未损坏）的概率。接下来 $N$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$-10^9 \leq x_i, y_i \leq 10^9$），表示每个军事基地的位置。接下来 $M$ 行，每行包含两个整数 $x_j$ 和 $y_j$（$-10^9 \leq x_j, y_j \leq 10^9$），表示每个通信塔的位置。保证没有两个建筑（即军事基地或通信塔）位于同一位置。同时保证在强风暴之前所有军事基地都是在线状态。

输出一行一个整数 $R$（$0 \leq R < 998\,244\,353$），使得 $P \equiv Q \cdot R \pmod{998\,244\,353}$，其中 $P$ 和 $Q$ 是互质的整数，且 $\frac{P}{Q}$ 是强风暴过后所有军事基地仍保持在线状态的概率。

#### 样例 #1 解释 每个发射器有 $50\%$ 的概率在强风暴中幸存。在此情况下，共有 $16$ 种等可能的结果，其中只有 $5$ 种结果会使所有军事基地在强风暴后仍保持在线，即活跃的（未损坏的）发射器集合为以下之一：$\{1, 2\}$、$\{1, 2, 3\}$、$\{1, 2, 3, 4\}$、$\{1, 2, 4\}$ 和 $\{1, 3, 4\}$。因此概率为 $\frac{5}{16}$，即 $P = 5$，$Q = 16$，$R = 686\,292\,993$。 #### 样例 #2 解释 除了第 $5$ 个发射器之外的所有发射器必须未损坏，才能使所有军事基地在强风暴后仍保持在线。每个发射器幸存概率为 $20\%$ 即 $\frac{1}{5}$，这种情况的概率为 $\left(\frac{1}{5}\right)^4 = \frac{1}{625}$。因此 $P = 1$，$Q = 625$，$R = 771\,443\,236$。 翻译由 DeepSeek 完成