solution

我们可以将问题转化为进行两次游戏,最终输出的序列相同的方案数。

为什么可以这么转化呢?我们尝试用式子表示这个新问题,对于一种序列,如果在一次游戏中取到他的方案数为,那么根据乘法原理,在两次游戏中都取到他的方案数就是,那么所有可能序列的方案数之和自然就是了。

那这个问题怎么做呢?我们设状态表示在第一次游戏中第一个序列还剩下了个球,第二个序列还剩下个求,在第二次游戏中第一个序列还剩下个球,第二个序列还剩下个求的方案数。
最后的答案自然就是

然后考虑转移,对于状态,我没枚举在每次游戏中最后加入的一个球。然后就可以得到转移方程如下:

f[i][j][k][t]=f[i-1][j][k-1][t] + f[i-1][j][k][t-1]+f[i][j-1][k - 1][t]+f[i][j-1][k][t-1]

根据状态的定义我们可以知道肯定满足。所以我们只需要枚举这三维就可以算出第4维,不需要枚举第四维。时空复杂度为

时间没问题,但空间会爆炸。所以将第一维滚动一下即可。

code

/*
* @Author: wxyww
* @Date:   2020-05-28 14:57:30
* @Last Modified time: 2020-05-28 16:07:27
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 510,mod = 1024523;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
int f[2][N][N];
char s[N],t[N];
int main() {
    int n = read(),m = read();
    scanf("%s",s + 1);
    scanf("%s",t + 1);

    f[0][0][0] = 1;
    for(int i = 0;i <= n;++i) {
        int tmp = i & 1;
        for(int j = 0;j <= m;++j) {
            for(int k = 0;k <= min(n,i + j);++k) {
                if(!i && !j && !k) {f[tmp][j][k] = 1;continue;}
                f[tmp][j][k] =  0;
                int tt = i + j - k;
                if(i && k && s[i] == s[k]) {
                    f[tmp][j][k] += f[tmp ^ 1][j][k - 1];
                    f[tmp][j][k] >= mod ? f[tmp][j][k] -= mod : 0;
                }
                if(i && tt && s[i] == t[tt]) {
                    f[tmp][j][k] += f[tmp ^ 1][j][k];
                    f[tmp][j][k] >= mod ? f[tmp][j][k] -= mod : 0;
                }
                if(j && k && t[j] == s[k]) {
                    f[tmp][j][k] += f[tmp][j - 1][k - 1];
                    f[tmp][j][k] >= mod ? f[tmp][j][k] -= mod : 0;
                }
                if(j && tt && t[j] == t[tt]) {
                    f[tmp][j][k] += f[tmp][j - 1][k];
                    f[tmp][j][k] >= mod ? f[tmp][j][k] -= mod : 0;
                }
            }
        }
    }

    cout<<f[n & 1][m][n]<<endl;
    return 0;
}