转化

容易发现题目中所求的其实可以看成取2次，而且2次取出的序列相同的方案数。

DP

考虑动态规划，设为第一次第1行取到第个,第2行取到第个，第二次第1行取到第个，第2行取到第个，其中且两次取到序列相同的方案数。答案即为。由于空间不够根据可以压掉一维，由于只与和有关所以可以滚动一维。最后时间复杂度空间复杂度。

CODE

#include<bits/stdc++.h>
using namespace std;
#define I inline 
#define ri register int
#define ll long long
#define For(i , x , y) for(ri i = x ; i <= y ; ++ i)
#define Next(i , u) for(ri i = head[u] ; i ; i = e[i].nxt)

I int read() {
    int s = 0 ,w = 1; char ch = getchar();
    while(ch < 48 || ch > 57) {if(ch == '-') w = -1; ch = getchar();}
    while(ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48) , ch = getchar();
    return s * w;
}

const int P = 1024523 , N = 505;

int n , m , f[10][N][N];
char s[N] , t[N];

signed main() {
    n = read() , m = read();
    scanf("%s%s" , s + 1 , t + 1);
    reverse(s + 1 , s + n + 1);
    reverse(t + 1 , t + m + 1);

    f[0][0][0] = 1;
    int u = 0 ;
    for(ri i = 0; i <= n ; ++ i , u ^= 1)
        For(j , 0 , m)
            For(k , 0 , n) {
                int l = i + j - k, tmp = f[u][j][k]; 
                if(l < 0 || l > m) continue;
                if(s[i + 1] == s[k + 1]) (f[u ^ 1][j][k + 1] += tmp) %= P;
                if(t[j + 1] == t[l + 1]) (f[u][j + 1][k] += tmp) %= P;
                if(s[i + 1] == t[l + 1]) (f[u ^ 1][j][k] += tmp ) %= P;
                if(t[j + 1] == s[k + 1]) (f[u][j + 1][k + 1] += tmp) %= P;
                f[u][j][k] = 0;
            }
    cout << f[u][m][n] << endl;
    return 0;
}