「清华集训 2017」某位歌姬的故事（组合计数 + 动态规划）

题目大意

「清华集训 2017」某位歌姬的故事（UOJ 346）

求满足下列条件的，长度为 $n$ 的正整数序列 $a$ 数量 $\bmod 998244353$ 的结果：

• $\forall a_i \le A$
• $\forall i \in [1, Q], \max { a_{l_i}, a_{l_i + 1}, \cdots, a_{r_i} } = m_i$

数据范围：$n, A \le 9 \times 10 ^ 8, Q \le 500$。

思路分析

先将序列离散化。对于离散化后的每一段，处理出这段可能达到的最大值。

考虑将限制按照最大值分组，最大值相同的限制一起处理，最后将每组的答案相乘得到总答案。其正确性是因为对于每段区间，它只会对包含它的限制的最小值（等于这段可能达到的最大值）贡献，所以贡献是不重不漏的。

于是问题就转化成了求满足下列条件的，长度为 $n’$ 的正整数序列 $a’$ 数量 $\bmod 998244353$ 的结果：

• $\forall a’_i \le A’$
• $\forall i \in [1, Q’], \max { a’_{l’_i}, a’_{l’_i + 1}, \cdots, a’_{r’_i} } = m’$

可以使用 DP 的方法来求解该问题。令 $\text{len}_i$ 表示第 $i$ 段的长度，预处理 $\text{mn}_i$ 表示右端点为第 $i$ 段区间的限制中左端点所在段的最小值。令 $\text{dp}_{i, j}$ 表示考虑到第 $i$ 位，最后一个 $A ^ {\prime}$ 在第 $j$ 段上的方案数。有两种转移：

• $\text{dp}_{i, j} \leftarrow \text{dp}_{i - 1, j} \times (A ^ {\prime} - 1) ^ {\text{len}_i} (j \in [\text{mn}_i, i - 1])$
• $\text{dp}_{i, i} \leftarrow \text{dp}_{i - 1, j} \times ((A ^ {\prime}) ^ {\text{len}_i} - (A ^ {\prime} - 1) ^ {\text{len}_i}) (j \in [0, i - 1])$

总时间复杂度 $O(T \times Q^2 \times \log n)$。

代码实现

#include <cstdio>