526互联

【前缀和优化 dp】CF1542E2 Abnormal Permutation Pairs (hard version) 题解

发布时间 2023-10-18 09:34:30作者: Pengzt

CF1542E2

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

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

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

易得转移 \(f_{i,j}=\sum\limits_{k=\max(j-i+1,0)}^{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。

参考上一个方法，交换 \(x,i\) 的 \(\Sigma\)，先不看前面 \(len\) 的枚举，同时改变一下 \(i\) 的上限方便转化，变为

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

交换 \(i,x\)

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

但这次好像没什么用，不妨先将后面与 \(h\) 有关的判断用函数 \(H(i,j)\) 替代。

\[\sum\limits_{i=2}^{len(len+1)/2}\sum\limits_{x=1}^{\min(i-1,len)}f_{len-1,i-x+1}\times(h_{len-1,i-x-1}-H(len-1,i)) \]

拆开括号

\[\sum\limits_{i=2}^{len(len+1)/2}\sum\limits_{x=1}^{\min(i-1,len)}f_{len-1,i-x+1}\times h_{len-1,i-x-1}-f_{len-1,i-x+1}\times H(len-1,i) \]

提出 \(H\)

\[\sum\limits_{i=2}^{len(len+1)/2}\sum\limits_{x=1}^{\min(i-1,len)}f_{len-1,i-x+1}\times h_{len-1,i-x-1}-H(len-1,i)\times\sum\limits_{x=1}^{\min(i-1,len)}f_{len-1,i-x+1} \]

发现 \(f,h\) 的第二维只相差 \(2\)，可以直接处理出来，后面的 \(f\) 可以用 \(g\) 来替代。

定义 \(s_{i,j}=\left\{ \begin{aligned} 0 (j<2)\\ \sum\limits_{k=2}^{j}h_{i,k-2}\times f_{i,k}(j\ge 2) \end{aligned} \right. \)

故最终式子为

\[\sum\limits_{i=2}^{len(len+1)/2}s_{len-1,i}-s_{len-1,i-len}[i\ge len]-H(len-1,i)\times(g_{len-1,i}-g_1[i\le len]-g_{len-1,i-len}[i>len]) \]

显然这里的时间复杂度为 \(\mathcal{O}(n^2)\)。

空间若全开 \(\mathcal{O}(n^3)\) 是不能过的，可以只将 \(f\) 开为三维，当然也可以使用滚动数组降为 \(\mathcal{O}(n^2)\)。

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

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

代码：

const int N=510,M=N*N/2;
int n,m,ans;
int f[M],g[M],h[M],s[M],sum[M];

int main(){
	cin>>n>>m;
	sum[0]=1;
	for(int i=1;i<=3;i++){
		for(int j=0;j<=i*(i-1)/2;j++)
			f[j]=(sum[j]-(j>=i?sum[j-i]:0)+m)%m;
		sum[0]=f[0];
		for(int j=1;j<=i*(i+1)/2;j++)
			sum[j]=(sum[j-1]+f[j])%m;
	}
	for(int len=4;len<=n;len++){
		g[0]=h[0]=f[0];
		for(int i=1;i<=len*(len-1)/2;i++) g[i]=(g[i-1]+f[i])%m,h[i]=(h[i-1]+g[i])%m;
		s[0]=s[1]=0;
		for(int i=2;i<=len*(len-1)/2;i++) s[i]=(s[i-1]+1ll*h[i-2]*f[i]%m)%m;
		int res=0;
		for(int i=2;i<=len*(len-1)/2;i++){
			res=((ll)res+s[i]-(i>len?s[i-len]:0)+m)%m;
			int sum=(g[i]-(i>len?g[i-len]:g[1])+m)%m;
			res=(res+1ll*sum*(m-(i>len?h[i-len-1]:0))%m)%m;
		}
		ans=(1ll*len*ans%m+res)%m;
		for(int j=0;j<=len*(len-1)/2;j++)
			f[j]=(sum[j]-(j>=len?sum[j-len]:0)+m)%m;
		sum[0]=f[0];
		for(int j=1;j<=len*(len+1)/2;j++)
			sum[j]=(sum[j-1]+f[j])%m;
	}
	cout<<ans<<endl;
	return 0;
}