[bzoj1566][NOI2009]管道取珠

来自FallDream的博客，未经允许，请勿转载，谢谢。

---

n<=500

神题......

发现这个平方可以看作两个序列相同的对数  然后就可以表示状态了。

f[i][j][k]表示两个序列各选了i个，第1个序列在第一行选了j个，第二个序列在第二行选了k个，他们相同的方案数

转移比较简单，枚举两个序列各填哪一位即可。

复杂度n^3

#include<iostream>

#include<cstdio>

#include<cstring>

#define MN 500

#define mod 1024523

using namespace std;

inline int read()

{

    int x =  , f = ; char ch = getchar();

    while(ch < '' || ch > ''){ if(ch == '-') f = -;  ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

int f[][][],n,m;

char A[MN+],B[MN+];

inline void R(int&x,int y){x+=y;x>=mod?x-=mod:;}

int main()

{

    n=read();m=read();

    scanf("%s",A+);scanf("%s",B+);

    f[][][]=;

    for(int i=,now=,pre=;i<n+m;++i)

    {

        for(int j=;j<=min(i,n);++j)

            for(int k=;k<=min(i,n);++k)

            {

                int J=i-j,K=i-k;

                if(j<n&&k<n&&A[j+]==A[k+]) R(f[now][j+][k+],f[pre][j][k]);

                if(j<n&&K<m&&A[j+]==B[K+]) R(f[now][j+][k],f[pre][j][k]);

                if(J<m&&k<n&&B[J+]==A[k+]) R(f[now][j][k+],f[pre][j][k]);

                if(J<m&&K<m&&B[J+]==B[K+]) R(f[now][j][k],f[pre][j][k]);

            }

        swap(now,pre);

        memset(f[now],,sizeof(f[now]));

    }

    printf("%d\n",f[(n+m)&][n][n]);

    return ;

}