题目

题目概要：
这道题目十分的长。我就来简述一下。
有一个三叉管道，两个管子装黑白两色的球。我们已知两个管子里面球的序列。
这两个管子的球全部进入到第三个管子中，第i种小球的排列方式有种。
求对1024523的余数。

输入描述：
第一行包含两个整数n,m，分别表示上下两个管道中球的数目。
第二行为一个AB字符串，长度为n，表示上管道中从左到右球的类型。其中A表示浅色球，B表示深色球。
第三行为一个AB字符串，长度为m，表示下管道中的情形。

输出描述：
仅包含一行，即为除以1024523的余数。

解析

知识点

  • 这道题是当然不可能是一道直接计算的题目。这道题是一道dp的题目。

看题目

  1. 首先我们来看题目，我们既然知道不能直接计算，那我们就要从理解这个公式的角度去写题目。
  2. 然后这道题目我们显然已经知道ai是啥了，但是我们现在要求ta的平方。说到平方，会想到啥？概率之积啊。
  3. 也就是说，我们现在可以把这道题看成是两个管道在对答案进行求解。

  • 写到了dp就不得不说的话：动态规划最重要的就是递推和dp数组的含义。

算法解析

  1. 我们知道了怎么写之后呢，我们就要想一下，我们如果不用公式该怎么求每一种情况的答案。
  2. 这当然就会用到我们的动态规划dp了（数据范围也是提示）：不过这一道题要对两组管子进行dp罢了。
  3. 我们能想到，枚举每一种管子里面的情况，自然就有了dp[i][j][k][l]，分别表示第一组的上下管子和第二组的上下管子数目。
  4. 我们数据范围是500，所以我们要想办法去压缩维度，压缩空间。这里我们就发现，最多塞下两个维度。
  5. 所以我们找找规律，就知道这两个装置是一样的，所以我们知道了i + j = k + l。那么l维我们就不要啦，因为可以算出来。
  6. 接下来因为我们的递推是一直在往前走的（最后答案只要是最后一个，而且过程中不用拿来计算），所以我们不需要保存过程中的东西咯，只要前后相邻的两个用于递推就可以了。
  7. 那么我们就可以将第一维度换成滚动数组。

算法操作

  1. 首先，我们先分三层循环进行递推。分别表示三个维度。
  2. 第一个维度，我们用1和0表示，所以我们定义一个cur变量保存第一个数，cur ^ 1就是相对的数（1的话就是0，0的就是1）。用于表示相邻。
  3. 然后就是递推了： 
    int& last = dp[cur][j][k];
if (s1[i + 1] == s1[k + 1]) 
        dp[cur ^ 1][j][k + 1] = (dp[cur ^ 1][j][k + 1] + last) % MOD;
if (s1[i + 1] == s2[l + 1]) 
     dp[cur ^ 1][j][k] = (dp[cur ^ 1][j][k] + last) % MOD;
if (s2[j + 1] == s1[k + 1]) 
     dp[cur][j + 1][k + 1] = (dp[cur][j + 1][k + 1] + last) % MOD;
if (s2[j + 1] == s2[l + 1]) 
    dp[cur][j + 1][k] = (dp[cur][j + 1][k] + last) % MOD;
last = 0;

打代码：

  1. 输入变量咯。
  2. 然后循环dp。
  3. 输出最后一个。
  4. 看我代码趴~

AC代码 

#include <iostream>
#include <string>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MOD = 1024523;
const int MAX = 507;
int n, m;
int dp[2][MAX][MAX];
string s1, s2;
//全局变量区

int main() {
    IOS;
    cin >> n >> m >> s1 >> s2;
    s1 = " " + s1; s2 = " " + s2;
    dp[0][0][0] = 1; int cur = 0;
    for (int i = 0; i <= n; i++, cur ^= 1)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k <= n; k++) {
                int l = i + j - k;
                int& last = dp[cur][j][k];
                if (l < 0 || l > m) continue;
                if (s1[i + 1] == s1[k + 1]) 
                    dp[cur ^ 1][j][k + 1] = (dp[cur ^ 1][j][k + 1] + last) % MOD;
                if (s1[i + 1] == s2[l + 1]) 
                    dp[cur ^ 1][j][k] = (dp[cur ^ 1][j][k] + last) % MOD;
                if (s2[j + 1] == s1[k + 1]) 
                    dp[cur][j + 1][k + 1] = (dp[cur][j + 1][k + 1] + last) % MOD;
                if (s2[j + 1] == s2[l + 1]) 
                    dp[cur][j + 1][k] = (dp[cur][j + 1][k] + last) % MOD;
                last = 0;
            }
    cout << dp[cur][m][n] << endl;
    return 0;
}
//函数区