题解 P6693 【谷歌翻(sheng)译(cao)机】

· · 题解

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]。

代码如下：

#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。