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; }