NC17621 管道取珠

思路：
如果这道题 $(n+m)$ 比较小，可以考虑二进制枚举，对于每种状态进行平方求和，但是这里n，m太大，肯定不够用。所以考虑转换模型。
对于这道题，是两次方，可以转化成2个人玩这个游戏然后局面相同的方案数。
然后开始构建dp的模型，dp[i][j][k][l]表示第一个人从管道1拿i个，管道2拿j个，第二个人从管道1拿k个，管道2拿l个两人序列相同的方案，但是四维DP不论时间空间都不允许。然后我们发现 $l==i+j-k$ ，所以第思维可以去掉。接着考虑状态转移。
1.考虑状态 $int$ $\&x=dp[i][j][k]，l==i+j-k$ 。

2.如果 $a[i+1]==a[k+1]$ ，表示第一个人管道1多选了一个，第二个人管道1多选了一个，所以有： $dp[i+1][j][k+1]=(dp[i+1][j][k+1]+x)%mod;$

3.如果 $a[i+1]==b[l+1]$ ，表示第一个人管道1多选了一个，第二个人管道2多选了一个，所以有： $dp[i+1][j][k]=(dp[i+1][j][k]+x)%mod;$

4.如果 $b[j+1]==a[k+1]$ ，表示第一个人管道2多选了一个，第二个人管道1多选了一个，所以有： $dp[i][j+1][k+1]=(dp[i][j+1][k+1]+x)%mod;$

5.如果 $b[j+1]==b[l+1]$ ，表示第一个人管道2多选了一个，第二个人管道2多选了一个，所以有： $dp[i][j+1][k]=(dp[i][j+1][k]+x)%mod;$

6.最后的结果就是 $dp[n][m][n];$

再看如果我们三层循环去枚举i，j，k，可以发现i只会向下更新不会往上更新，那么这个地方第一维可以用个滚动数组表示一下。这个时候1的表述就起作用了：

int &x=dp[now][j][k];//引用
。。。。
x=0;//状态转移后上一维就没有用了，相当于dp[now][j][k]=0;

Code:

#include<bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int mod=1024523;
int n,m;
int dp[2][507][507];
string a,b;
int main() {
    js; cin>>n>>m>>a>>b;
    a="#"+a,b="#"+b;
    dp[0][0][0]=1;
    for(int i=0,now=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]=(dp[now^1][j][k+1]+x)%mod;
        if(a[i+1]==b[l+1]) dp[now^1][j][k]=(dp[now^1][j][k]+x)%mod;
        if(b[j+1]==a[k+1]) dp[now][j+1][k+1]=(dp[now][j+1][k+1]+x)%mod;
        if(b[j+1]==b[l+1]) dp[now][j+1][k]=(dp[now][j+1][k]+x)%mod;
        x=0;
    }
    cout<<dp[!(n&1)][m][n];
    return 0;
}