Description

给定两个管道，任意取珠子，有 种情况，定义 为取 个珠子的方案数总和
现在要求

Solution

对于 ，考虑其意义，从函数合成的角度，可以理解为两个相同的过程相互合成，即两次从管道取珠相同的方案数，那么这个计数问题我们可以用 去解决了，考虑 为第一个管道取了 个，第二个管道取了 个，第三个管道取了 个，第四个管道取了 个，显然空间复杂度过高，考虑优化一下， ， 可以少一维枚举，然后呢， 只会和 有关系，所以滚动数组优化一下，答案为 , 最终空间复杂度 , 时间复杂度为
另外，这道题卡常，可以试试开 O3 还有减少取模次数去优化常数。

Code

#pragma GCC optimize(3)
#include<bits/stdc++.h>

using namespace std;

const int mod = 1024523;

int dp[2][1005][1005];
void fun(int &x) {
  if(x >= mod) {
    x %= mod;
  }
}
char s[1005], t[1005];
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  int n, m;
  scanf("%d %d", &n, &m);
  scanf("%s %s", s + 1, t + 1);
  dp[0][0][0] = 1;
  for(int i = 0; i <= n; i++) {
    for(int j = 0; j <= m; j++) {
      for(int k = 0; k <= min(n, i + j); k++) {
        int l = i + j - k;
        if(!i && !j && !k) {
          dp[i & 1][j][k] = 1;
          continue;
        }
        dp[i & 1][j][k] = 0;
        if(i && k && s[i] == s[k]) {
          dp[i & 1][j][k] += dp[(i + 1) & 1][j][k - 1];
          fun(dp[i & 1][j][k]);

        } 
        if(i && l && s[i] == t[l]) {
          dp[i & 1][j][k] += dp[(i + 1) & 1][j][k];
          fun(dp[i & 1][j][k]);
        }
        if(j && k && t[j] == s[k]) {
          dp[i & 1][j][k] += dp[i & 1][j - 1][k - 1];
          fun(dp[i & 1][j][k]);
        }
        if(j && l && t[j] == t[l]) {
          dp[i & 1][j][k] += dp[i & 1][j - 1][k];
          fun(dp[i & 1][j][k]);
        }
      } 
    }
  }
  cout << dp[n & 1][m][n] << "\n";
  return 0;
}