这是一道DP神题,直到我写下这句题解时也没有想明白……
首先，这道题要我们求所有（不同输出序列的方案数）的平方和，于是我们当然就想到求所有不同输出序列的方案数……（大雾） 。这道题一个巧妙的地方就在于对问题的转化。（以下摘自BYVoid大神的题解）
假设同时有两个人X & Y在玩这个游戏，设X从up取了i个珠子（不一定连续），从down取了j个珠子，取出来的珠子组成的序列为Q，操作序列为x，Y从up取了k个珠子，从down取了l个珠子，取出来的珠子组成的序列也为Q，操作序列为y，那么我们就得到了一个有序对（x，y），f[i][j][k][l]即表示有序对（x，y）的数量。两个有序对不相同当且仅当x和y不同时相同。
下面证明f[i][j][k][l]即为所求。
已知：取出珠子的序列为Q，x和y分别为一种取珠方法（可相同）， 取出Q的方案数为a；
求证：有序对（x，y）的数量等于a。
因为取出Q的方案数为a，所以x & y都有a种取值，且x & y彼此独立，故对于x的每一个取值，y都有a种取值，故有序对（x，y）的数量为a，命题得证。
博主是个超级大傻*，连空间优化到n都不会，请各路大神指教。
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <complex>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define rg register
#define ll long long
using namespace std; inline int gi()
{
rg int r = ; rg bool b = ; rg char c = getchar();
while (c < '' || c > '') { if (c == '-') b = ; c = getchar(); }
while (c >= '' && c <= '') { r = r * + c - '', c = getchar(); }
if (b) return r; return -r;
} const int inf = , N = , MOD = ;
int n,m,f[N][N][N];
char S[N],X[N]; inline void input()
{
freopen ("!.in", "r", stdin);
n=gi(), m=gi();
scanf("%s%s",S+,X+);
} inline void output()
{
freopen ("!.out", "w", stdout);
printf("%d\n",f[n][m][n]);
} inline void cal(int &t,int d) { t+=d; if (t >= MOD) t-=MOD; } inline void solve()
{
int i,j,k,l,tmp;
f[][][]=;
for (i=; i<=n; i++)
for (j=; j<=m; j++)
for (k=; k<=n; k++)
{
tmp=f[i][j][k], l=i+j-k;
if (!tmp || !l || l > m) continue;
if (S[i+] == S[k+])
cal(f[i+][j][k+],tmp);
if (X[j+] == S[k+])
cal(f[i][j+][k+],tmp);
if (S[i+] == X[l+])
cal(f[i+][j][k],tmp);
if (X[j+] == X[l+])
cal(f[i][j+][k],tmp);
}
} int main()
{
input();
solve();
output();
return ;
}
Update
博主终于会把空间优化到n^2辣！！！
PS：记得要清零！！！
#include <bits/stdc++.h>
#define rg register
#define ll long long
using namespace std; inline int gi()
{
rg int r = ; rg bool b = ; rg char c = getchar();
while (c < '' || c > '') { if (c == '-') b = ; c = getchar(); }
while (c >= '' && c <= '') { r = r * + c - '', c = getchar(); }
if (b) return r; return -r;
} const int inf = , N = , MOD = ;
int n,m,f[][N][N];
char S[N],X[N]; inline void input()
{
n=gi(), m=gi();
scanf("%s%s",S,X);
} inline void cal(rg int &t,rg int d)
{
t+=d;
if (t >= MOD)
t-=MOD;
} inline void solve()
{
rg int i,j,k,p,q,l,r,now,lst;
f[][][]=, now=;
for (k=; k<n+m; ++k) //枚举一共选了多少个，因为每次更新都会多选一个，所以只需枚举到 n+m-1
{
l=max(k-m,), r=min(k,n); //计算 S 管道取珠的数量范围
lst=now, now^=;
for (i=l; i<=r; ++i) //分别枚举序列 x，y
for (j=l; j<=r; ++j)
{
p=k-i, q=k-j; //i，j 表示 S 管道取的数量，p，q表示 X 管道的数量
if (!f[lst][i][j])
continue;
if (S[i] == S[j])
cal(f[now][i+][j+],f[lst][i][j]);
if (S[i] == X[q])
cal(f[now][i+][j],f[lst][i][j]);
if (X[p] == S[j])
cal(f[now][i][j+],f[lst][i][j]);
if (X[p] == X[q])
cal(f[now][i][j],f[lst][i][j]);
f[lst][i][j]=; //每次更新后要记得清零
}
}
printf("%d\n",f[now][n][n]);
} int main()
{
input();
solve();
return ;
}