自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:23:08，当前版本为作者最后更新于2020-07-24 20:53:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Upd on 2020.11.18：补充说明

题面传送门。

题意简述：给定两个字符串 $A,B$，长度分别为 $n,m$。构造长度为 $k$ 的两个数列 $p,q$ 满足 $p_1=q_1=0,p_k=n,q_k=m,p_i<p_{i+1},q_i<q_{i+1}$ 且 $A_{p_i}=B_{q_i}$（字符串下标从 $1$ 开始），则其权值为 $\sum (p_i-p_{i-1}-1)^2+(q_i-q_{i-1}-1)^2$。求所有这样的数列 $p,q$ 的权值之和。

---

显然有一个 $n^4$ 的 DP：

设 $f_{i,j}$ 表示数列 $p$ 以 $i$ 结尾，数列 $q$ 以 $j$ 结尾的所有数列 $p,q$ 的权值之和。
设 $num_{i,j}$ 表示数列 $p$ 以 $i$ 结尾，数列 $q$ 以 $j$ 结尾的方案数。

那么有转移方程

$$f_{i,j}=\begin{cases}\sum_{k<i,\ l<j} f_{k,l}+num_{k,l}\times[(i-k-1)^2+(j-l-1)^2]\quad&(A_i=B_j)\\0&(A_i\neq B_j)\end{cases} $$$$num_{i,j}=\begin{cases}\sum_{k<i,\ l<j}num_{k,l}\quad&(A_i=B_j)\\0&(A_i\neq B_j)\end{cases} $$

不难发现这样转移是 $O(n^2)$ 的，因为有 $O(n^2)$ 个状态，所以时间复杂度为 $O(n^4)$，无法接受。

不难看出 $num$ 的转移就是一个二维前缀和形式，用二维前缀和优化 DP 可以将 $num_{i,j}$ 的转移降为 $O(1)$。但是 $f$ 似乎不能这么优化？

当然可以。显然 $\sum f_{k,l}$ 是可以前缀和优化的，我们将后面一部分单独拎出来看：

$$\sum num_{k,l}\times[(i-k-1)^2+(j-l-1)^2]$$

记 $num_{k,l}=S$，平方部分拆开来就能得到

$$\begin{aligned}&\sum S\times(i^2-2i+1-2ki+2k+k^2+j^2-2j+1-2lj+2l+l^2)\\=&\sum S\times[(i^2+j^2-2i-2j+2)+(k^2+l^2+2k+2l)-2ki-2lj]\\=&\sum \color{red}S\color{black}\times(i^2+j^2-2i-2j+2)+\color{blue}S\times(k^2+l^2+2k+2l)\color{black}-\color{orange}2Sk\color{black}i-\color{green}2Sl\color{black}j\end{aligned} $$

将上式与 $i,j$ 无关的二维前缀和预处理出来（即红色的 $\sum num_{k,l}$，蓝色的 $\sum num_{k,l}\times(k^2+l^2+2k+2l)$，橙色的 $2\sum num_{k,l}\times k$ 和绿色的 $2\sum num_{k,l}\times l$）即可 $O(1)$ 转移 $f$。

答案即为 $\sum f_{i,j}+num_{i,j}\times[(n-i)^2+(m-j)^2]$。

• 需要注意的是只有当 $A_i=B_j$ 的时候柿子才能算入贡献。

代码如下：

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N=3e3+5;
const int mod=1e9+7;

ll pw[N],f[N][N],num[N][N],sumf[N][N],sumn[N][N],cons[N][N],delk[N][N],dell[N][N],ans;
string s,t;
int n,m;

void add(ll &x,ll y){
	x+=y%mod;
	if(x>=mod)x-=mod; if(x<0)x+=mod;
}

int main() {
	for(int i=1;i<N;i++)pw[i]=i*i;
	cin>>n>>m>>s>>t;
	for(int i=0;i<=max(n,m);i++)sumn[i][0]=sumn[0][i]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(s[i-1]==t[j-1]){
				f[i][j]=sumf[i-1][j-1],num[i][j]=sumn[i-1][j-1];
				add(f[i][j],(pw[i]+pw[j]-2*i-2*j+2)%mod*sumn[i-1][j-1]+cons[i-1][j-1]);
				add(f[i][j],-delk[i-1][j-1]*i-dell[i-1][j-1]*j);
				add(ans,f[i][j]+num[i][j]*(pw[n-i]+pw[m-j]));
			}
			sumf[i][j]=(sumf[i-1][j]+sumf[i][j-1]-sumf[i-1][j-1]+f[i][j]+mod)%mod;
			sumn[i][j]=(sumn[i-1][j]+sumn[i][j-1]-sumn[i-1][j-1]+num[i][j]+mod)%mod;
			cons[i][j]=(cons[i-1][j]+cons[i][j-1]-cons[i-1][j-1]+num[i][j]*(pw[i]+pw[j]+2*i+2*j)+mod)%mod;
			delk[i][j]=(delk[i-1][j]+delk[i][j-1]-delk[i-1][j-1]+num[i][j]*2*i%mod+mod*2)%mod;
			dell[i][j]=(dell[i-1][j]+dell[i][j-1]-dell[i-1][j-1]+num[i][j]*2*j%mod+mod*2)%mod;
		}
	cout<<(ans+pw[n]+pw[m])%mod<<endl;
	return 0;
}

求赞 qwq。