P16086 [ICPC 2024 NAC] House Deconstruction

在圆环之国，有一个圆周上均匀分布着若干点。相邻两点之间的距离为 $ 1 $。 圆周上的点上有人和房屋。每个点上要么有一个人，要么有一个空房子，要么什么都没有。每个人都想走到一个不同的房屋。每个房屋最多只能容纳一个人。人们只能沿着圆周行走，不能穿过圆内。 目前，房屋的数量多于人的数量，因此你想拆除一些房屋。假设你拆除了一组房屋 $ S $。记 $ f(S) $ 为让每个人走到一个不同的未被拆除的房屋所需的最小总行走距离。 请计算 $ f(S) $ 的最小可能值，以及有多少组房屋集合 $ S $ 能达到这个最小值。由于 $ S $ 的数量可能很大，请输出其对 $ 998,244,353 $ 取模的结果。

输入的第一行包含三个整数 $ x $、$ n $ 和 $ m $（$ 1 \le n < m \le 2 \cdot 10^5 $，$ n + m \le x \le 10^9 $），其中 $ x $ 是圆周上的点数，$ n $ 是人数，$ m $ 是房屋数。点的编号为 $ 1 $ 到 $ x $，且点 $ x $ 与点 $ 1 $ 相邻。 接下来的 $ n + m $ 行，每行包含两个标记：一个整数 $ p $（$ 1 \le p \le x $）和一个字符 $ t $（$ t \in \{\text{P}, \text{H}\} $），其中 $ p $ 表示人或房屋的位置，$ t $ 表示该点的类型（P 代表人，H 代表房屋）。所有位置互不相同，并且位置按递增顺序给出。

输出两行。第一行输出 $ f(S) $ 的最小可能值。第二行输出达到该最小值的集合 $ S $ 的数量，对 $ 998,244,353 $ 取模。

**样例解释** 对于第一个样例，最小总行走距离为 $ 2 $。我们可以拆除的房屋集合有 $ \{2,5\} $、$ \{4,5\} $ 或 $ \{5,6\} $。 对于第二个样例，我们可以拆除的房屋集合为 $ \{6,31415926\} $，最小总行走距离为 $ 4 $。请注意，即使有多种方式达到最小行走距离，由于拆除的房屋集合相同，只被计数一次。 翻译由 DeepSeek V3.2 完成