Luogu

BZOJ

分析

$\mathrm{DP}$ 。

平方的话,相当于做两次。那么原式的意思就是做两次得到了相同的串的方案数。

设 $f[i][j][k][l]$ 表示第一次取了 $A$ 中的前 $i$ 个、 $B$ 中的前 $j$ 个,第二次取了 $A$ 中的前 $k$ 个、 $B$ 中的前 $l$ 个的方案数。

注意到 $i+j=k+l$ ,所以可以省去 $l$ 的一维。然后 $i$ 那一维可以滚动数组优化一下。

转移比较简单,直接分类讨论即可。

具体实现及细节见代码。

代码

开 $\mathrm{O2}$ 可过。

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

const int N=500+10;
const int mod=1024523;

int n,m;
char a[N],b[N];
int f[2][N][N];

inline void add(int& a,int b) { a=(a+b)%mod; }

int main() {
    scanf("%d%d%s%s",&n,&m,a+1,b+1);
    f[0][0][0]=1;
    for (re int i=0;i<=n;++i) {
        int now=i&1,nxt=now^1;
        memset(f[nxt],0,sizeof(f[nxt]));
        for (re int j=0;j<=m;++j)
            for (re int k=0;k<=i+j;++k) {
                int l=i+j-k;
                if (a[i+1]==a[k+1]) add(f[nxt][j][k+1],f[now][j][k]);
                if (a[i+1]==b[l+1]) add(f[nxt][j][k],f[now][j][k]);
                if (b[j+1]==a[k+1]) add(f[now][j+1][k+1],f[now][j][k]);
                if (b[j+1]==b[l+1]) add(f[now][j+1][k],f[now][j][k]);
            }
    }
    printf("%d\n",f[n&1][m][n]);
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 14 PM