很强的题目，这启发我们看到平方方案数的时候要考虑两个人分开统计相同的方案数

对于这道题就是找到两个人，然后每次两个人分别去取这两个字符串内的字符，最终相同的方案数，不难证明这就是 $\sum_{i=1}^{k} a_i^2$

然后我们考虑设dp转移方程

我们考虑 $dp_{i,j,k}$ 表示两个人已经都取了 $i$ 位，其中第一个人在 $A$ 中取了 $j$ 个字符，第二个人在 $A$ 中取了 $k$ 个字符，则我们不难算出第一个人在 $B$ 中取了 $i-j$ 个字符，第二个人在 $B$ 中取了 $i-k$ 个字符

然后我们考虑转移

因为我们发现只有两个人取的长度相同才有可能是相同的方案，所以我们先看如果两个人都是取的 $A$ 中的字符，并且两个字符相同，则有：

若第一个人取的是 $A$ ，第二个人取的是 $B$ 则有：

类似的，其他转移方程

然后我们考虑初值，显然地，$dp_{0,0,0}=1$ 答案为 $dp_{n+m,n,n}$

最后我们发现会又MLE又TLE，所以卡常+滚动数组优化

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 505
#define int long long
using namespace std;
bool Test_MLE_start;
const int mod=1024523;
int T=1,n,m;
char sa[N],sb[N];
int a[N],b[N],dp[2][N][N];
inline int reads(){
	char c=getchar();
	int sum=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		sum=(sum<<3)+(sum<<1)+(c^'0');
		c=getchar();
	}
	return sum*f;
}
inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
int add(int a,int b){
	int c=a+b;
//	cout<<a<<" "<<b<<"\n";
	if(c>=mod) c%=mod;
	return c;
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	T=reads();
	while(T--){
		clr();
		n=reads(),m=reads();
		scanf("%s%s",sa+1,sb+1);
		reverse(sa+1,sa+n+1),reverse(sb+1,sb+m+1);
		int now=0;
		dp[0][0][0]=1;
		for(int i=1;i<=n+m;i++){
			now^=1;
			memset(dp[now],0,sizeof(dp[now]));
//			cout<<i<<" "<<now<<"\n";
			for(int j=max(0ll,i-m);j<=min(i,n);j++){
				for(int k=max(0ll,i-m);k<=min(i,n);k++){
					if(j&&k&&sa[j]==sa[k]) dp[now][j][k]=add(dp[now][j][k],dp[now^1][j-1][k-1]);
					if(j&&i-k&&sa[j]==sb[i-k]) dp[now][j][k]=add(dp[now][j][k],dp[now^1][j-1][k]);
					if(i-j&&k&&sb[i-j]==sa[k]) dp[now][j][k]=add(dp[now][j][k],dp[now^1][j][k-1]);
					if(i-j&&i-k&&sb[i-j]==sb[i-k]) dp[now][j][k]=add(dp[now][j][k],dp[now^1][j][k]);
				}
			}
		}
		printf("%lld\n",dp[now][n][n]);
	}
	return 0;
}

他这个Σ${a_i}^2$看上去不知道该怎么做，但是，仔细想一想发现他就是：

先找到两个人，两个a，两个b，最后这两个人得到的序列相同的情况有多少种。

设dp[k][i][j]表示现在两个人各取了k位，第一个人在a中取了i位，第二个人在a中取了j位。

初状态：dp[0][0][0]=1

目标状态：dp[n+m][n][n]

转移：枚举k，i，j，然后写四个if来判断能否转移。

使用滚动数组否则空间会炸，而且要注意卡长。

原题洛谷P1758

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int n,m;
string a,b;
int dp[2][505][505];
signed main() {
	std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>a>>b;
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	a=" "+a,b=" "+b;
	int nw=0;
	dp[0][0][0]=1;
	for(int k=1; k<=n+m; ++k) {
		nw^=1;
		for(int i=0; i<=n; ++i) {
			for(int j=0; j<=n; ++j) {
				dp[nw][i][j]=0; 
				if(i&&j&&a[i]==a[j]) {
					dp[nw][i][j]+=dp[nw^1][i-1][j-1];
					if(dp[nw][i][j]>=mod)dp[nw][i][j]-=mod; 
				}
				if(i&&k-j&&a[i]==b[k-j]) {
					dp[nw][i][j]+=dp[nw^1][i-1][j];
					if(dp[nw][i][j]>=mod)dp[nw][i][j]-=mod;
				}
				if(k-i&&j&&b[k-i]==a[j]) {
					dp[nw][i][j]+=dp[nw^1][i][j-1];
					if(dp[nw][i][j]>=mod)dp[nw][i][j]-=mod;
				}
				if(k-i&&k-j&&b[k-i]==b[k-j]) {
					dp[nw][i][j]+=dp[nw^1][i][j];
					if(dp[nw][i][j]>=mod)dp[nw][i][j]-=mod;
				}
			}
		}
	}
	cout<<dp[nw][n][n]<<"\n";
	return 0;
}