「LOJ 575」不等关系（容斥原理 + 多项式）

题目大意

「LOJ 575」不等关系

给定一个长度为 $n$ 的字符串 $s$，$s_i \in {<, >}$。要求计数长度为 $n + 1$ 的排列 $a$，满足 $a_i < a_{i + 1}$ 当且仅当 $s_i$ 为 $<$，模数为 $998244353$。

数据范围：$n \le 10^5$。

思路分析

首先想到一个状态数为 $n^2$ 的 $\text{dp}$，但是发现它不能优化。于是考虑容斥。

对于所有 $<$，我们考虑把它容斥成 $\neq$ 的方案数减去 $>$ 的方案数。这样容斥后，问题就变成了字符串的每一位都是无限制或大于号，求方案数。假设第 $i$ 个大于号的连续段长度为 $\text{len}_i - 1$，则总方案数为 $\displaystyle \frac{n!}{\prod \text{len}_i!}$。这样，我们就得到了一个 $O(2^n)$ 的做法。

我们发现我们可以使用带容斥系数的 $\text{dp}$ 来解决这个问题。那么：

$$dp_{n} = \begin {cases} 1 & (n = 0)\\ \displaystyle \sum_{i = 0}^{n - 1} [i = 0 \text{ or } s_i = \text{<}] \cdot dp_{i} \cdot \frac{(-1) ^ {\text{cnt}_{n - 1} - \text{cnt}_i}}{(n - i)!} & (n \ge 1) \end {cases}$$

其中 $\text{cnt}_i$ 表示前 $i$ 个位置有多少个 $\text{<}$，而答案就等于 $dp_{n + 1} \times (n + 1)!$。这样做的时间复杂度为 $O(n^2)$。

发现这个式子可以使用分治 FFT 优化。时间复杂度 $O(n \log^2 n)$，可以通过本题。

代码实现

#include <bits/stdc++.h>