【前缀和优化 dp】CF1542E1 Abnormal Permutation Pairs (easy version) 题解-526互联

首先时间复杂度肯定是 \(\mathcal{O}(n^3)\) 的。

容易想到先枚举最长公共前缀，然后枚举 \(p_{len+1}\) 和 \(q_{len+1}\)，再枚举逆序对数进行统计。

令 \(f_{i,j}\) 表示有 \(j\) 个逆序对的 \(i\) 阶排列的个数。

易得转移 \(f_{i,j}=\sum\limits_{k=j-i+1}^{j}f_{i-1,k}\)，使用前缀和可以做到 \(\mathcal{O}(n^3)\)。

此时第一个数为 \(i\) 且逆序对数为 \(j\) 的 \(n\) 阶排列的个数显然为 \(f_{n-1,j-i+1}\)。

则答案可表示为

\[\sum\limits_{len=4}^{n}\dfrac{n!}{(n-len)!}(\sum\limits_{x=1}^{len-1}\sum\limits_{y=x+1}^{len}\sum\limits_{i=x+1}^{x+1+(len-1)(len-2)/2}\sum\limits_{j=y-1}^{i-1}f_{len-1,i-x+1}\times f_{len-1,j-y+1}) \]

默认 \(0!=1\)，这是 \(\mathcal{O}(n^7)\) 的。

将式子稍微转化一下：

\[\sum\limits_{len=4}^{n}\dfrac{n!}{(n-len)!}(\sum\limits_{x=1}^{len-1}\sum\limits_{y=x+1}^{len}\sum\limits_{i=x+1}^{x+1+(len-1)(len-2)/2}f_{len-1,i-x+1}\times (\sum\limits_{j=0}^{i-y}f_{len-1,j})) \]

用前缀和可优化至 \(\mathcal{O}(n^5)\)。

令 \(g_{i,j}=\sum\limits_{k=0}^{j}f_{i,k}\)。

用 \(g\) 替代：

\[\sum\limits_{len=4}^{n}\dfrac{n!}{(n-len)!}(\sum\limits_{x=1}^{len-1}\sum\limits_{y=x+1}^{len}\sum\limits_{i=y}^{x+1-(len-1)(len-2)/2}f_{len-1,i-x+1}\times g_{len-1,i-y}) \]

直接看是不能再优化了，考虑交换一下后两个 \(\Sigma\) 的位置，并提出 \(f_{len-1,i-x+1}\)，变为：

\[\sum\limits_{len=4}^{n}\dfrac{n!}{(n-len)!}(\sum\limits_{x=1}^{len-1}\sum\limits_{i=x+1}^{x+1+(len-1)(len-2)/2}f_{len-1,i-x+1}\times(\sum\limits_{y=x+1}^{\min(i,n)}g_{len-1,i-y}) \]

发现可以继续使用前缀和优化。

再变一下：

\[\sum\limits_{len=4}^{n}\dfrac{n!}{(n-len)!}(\sum\limits_{x=1}^{len-1}\sum\limits_{i=x+1}^{x+1+(len-1)(len-2)/2}f_{len-1,i-x+1}\times\sum\limits_{y=i-min(i,n)}^{i-x-1}g_{len-1,y}) \]

令 \(h_{i,j}=\sum\limits_{k=0}^{j}g_{i,k}\)，带入原式：

\[\sum\limits_{len=4}^{n}\dfrac{n!}{(n-len)!}(\sum\limits_{x=1}^{len-1}\sum\limits_{i=x+1}^{x+1+(len-1)(len-2)/2}f_{len-1,i-x+1}\times (h_{len-1,i-x-1}-h_{len-1,i-len-1}\times[i>len])) \]

时间复杂度降至 \(\mathcal{O}(n^4)\)。

已经可以通过 E1.

时间复杂度：\(\mathcal{O}(n^4)\)。

空间复杂度：\(\mathcal{O}(n^3)\)。

评测记录