LibreOJ #575

「LibreOJ NOI Round #2」不等关系

题目描述：

给定一个字符串，仅包含 < 和 > 两种字符。你需要计算「使得\(p_i<p_{i+1}\)当且仅当 \(s_i\)为 < 的排列 \(p_1,p_2,\dots p_n\) 」的数量。

考虑容斥：<不满足即为>满足，故原问题转化为求满足多个连续段递增的排列数目。

利用FFT优化DP连续段即可。

\[ \begin{aligned} f_0=&1 \\ f_n=&\sum_{k<n}\mathrm{islt}(s_{k})(-1)^{cnt(n)-cnt({k+1})} {n\choose k} f_k \end{aligned} \]