题解 \(by\;zj\varphi\)
原题问的就是对于一个序列,其中有的数之间有大小关系限制,问有多少种方案。
设 \(dp_{i,j}\) 表示在前 \(i\) 个数中,第 \(i\) 个的排名为 \(j\)的方案数
方程:
\[f_{i,j}=\begin{cases} \sum\limits_{k=j}^{i-1} f_{i-1,k},(p_{i-1}<p_i)\\ \sum\limits_{k=1}^{j-1} f_{i-1,k},(p_{i-1}>p_i)\\ \end{cases} \]直接前缀和优化即可 \(\mathcal O\rm(n^2)\)