动态规划

参考zzugzx大佬题解 orz

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

管道取珠是小X很喜欢的一款游戏。在本题中，我们将考虑该游戏的一个简单改版。游戏画面如图1所示：

游戏初始时，左侧上下两个管道分别有一定数量的小球（有深色球和浅色球两种类型），而右侧输出管道为空。每一次操作，可以从左侧选择一个管道，并将该管道中最右侧的球推入右边输出管道。

例如，我们首先从下管道中移一个球到输出管道中，将得到图2所示的情况。


假设上管道中有n个球,下管道中有m个球，则整个游戏过程需要进行n+m次操作，即将所有左侧管道中的球移入输出管道。最终n +m个球在输出管道中从右到左形成输出序列。

爱好数学的小X知道，他共有C(n+m, n)种不同的操作方式，而不同的操作方式可能导致相同的输出序列。举个例子，对于图3所示的游戏情形：

们用A表示浅色球，B表示深色球。并设移动上管道右侧球的操作为U,移动下管道右侧球的操作为D，则共有C(2+1,1)=3种不同的操作方式,分别为UUD, UDU, DUU；最终在输出管道中形成的输出序列（从右到左）分别为BAB，BBA，BBA。可以发现后两种操作方式将得到同样的输出序列。

假设最终可能产生的不同种类的输出序列共有K种，其中第i种输出序列的产生方式(即不同的操作方式数目)有ai个。聪明的小X早已知道，

因此，小X希望计算得到

你能帮助他计算这个值么？由于这个值可能很大，因此只需要输出该值对1024523的取模即可(即除以1024523的余数)。

说明：文中C(n+m,n)表示组合数。组合数C(a,b)等价于在a个不同的物品中选取b个的选取方案数。


输入描述:

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

输出描述:

仅包含一行，即为除以1024523的余数
示例1

输入

复制 
2 1
AB
B

输出

复制 
5

题目给出求解的累加方案和，直接求解解决不了那怎么办，看大佬题解发现可以把问题转换过来。
题目给出的的方案数比较好求，那平方是不是能看成2个人玩这个游戏然后局面相同的情况呢！居然是可以的。
那么题目给我们求得的累加和就转换成了2个人玩这个弹珠游戏方案相同的方法数！震惊问题就这样得到转换了。
那么这个转换的问题任何求解，最原始的方法我们假设为第一个人第一行用了i第二行用了j。第二个人第一行拿了k，第二行拿了l相同的方法数。为什么说这个是最原始的方法，因为四维dp，时间空间都不允许你这么干……题目也没给范围
那么我们再进行优化，题目给出的是需要出来序列相同，那么长度一定相同，所以得到，那么l这一维可以直接省略不写。浓缩在三维即可。
再看如果我们三层循环去枚举i，j，k，可以发现i只会向下更新不会往上更新，那么这个地方第一维可以用个滚动数组表示一下。
至此我们就表示第一个人第一行用了i个珠子第二行用了j个珠子，第二个人第一行用了k个珠子，第二行用了i+j-k个珠子的相同方法数。最终输出就是答案了。

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1024523;
inline ll read() { ll 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; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 510 + 7; //500+7 TLE……
string a, b;
int n, m;
int dp[2][N][N];

int main() {
    js;
    cin >> n >> m >> a >> b;
    a = '#' + a, b = '#' + b;
    dp[0][0][0] = 1;
    int now = 0;
    for (int i = 0; i <= n; ++i, now ^= 1)
        for (int j = 0; j <= m; ++j)
            for (int k = 0; k <= n; ++k) {
                int l = i + j - k;
                if (l<0 || l>m)    continue;
                int& x = dp[now][j][k];
                if (a[i + 1] == a[k + 1])    (dp[now ^ 1][j][k + 1] += x) %= MOD;
                if (a[i + 1] == b[l + 1])    (dp[now ^ 1][j][k] += x) %= MOD;
                if (b[j + 1] == a[k + 1])    (dp[now][j + 1][k + 1] += x) %= MOD;
                if (b[j + 1] == b[l + 1])    (dp[now][j + 1][k] += x) %= MOD;
                x = 0; //滚动数组累加记得清零
            }
    cout << dp[now][m][n] << '\n';
    return 0;
}