Eva

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 2642  Solved: 1561
Description

Input

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

Output

仅包含一行，即为 Sigma(Ai^2) i从1到k 除以1024523的余数。

Sample Input

2 1
AB
B

Sample Output

5

HINT

样例即为文中(图3)。共有两种不同的输出序列形式，序列BAB有1种产生方式，而序列BBA有2种产生方式，因此答案为5。 【大致数据规模】 约30%的数据满足 n, m ≤ 12； 约100%的数据满足n, m ≤ 500。

/**************************************************************

    Problem: 1566

    User: ictsing

    Language: C++

    Result: Accepted

    Time:5948 ms

    Memory:3284 kb

****************************************************************/

 

//1566: [NOI2009]管道取珠

/*

设有ai种方法可以产生第i种输出序列

那么∑ai=c(n+m,n){1≤i≤k}

求∑(ai^2){1≤i≤k}

 

感觉这道题思路灰常好啊，

我们要观察ai^2与ai的关系，

当于操作两次，所得到的颜色序列一样的方案数，

f[i][j][p][q]上面选了j个，下面j个，第二次上面选了p个，下面选了q个的方案数

*/

#include <iostream>

#include <cstdio>

using namespace std;

const int mod = 1024523;

const int mt = 500+5;

int f[2][mt][mt],a[mt],b[mt];

char s[mt];

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

int main()

{ 

    int n=read(),m=read();

    scanf("%s",s+1);

    for(int i=1;i<=n;i++)

        a[i]=s[i]-'A'+1;

    scanf("%s",s+1);

    for(int i=1;i<=m;i++)

        b[i]=s[i]-'A'+1;

    int now=0;

    f[now][0][0]=1;

    for(int i=0;i<=n;i++)

    {

       for(int j=0;j<=m;j++)

        for(int k=0;k<=n;k++)

            f[now^1][j][k]=0;

       for(int j=0;j<=m;j++)

        for(int k=0;k<=n;k++)

        {

            if(a[i+1]==a[k+1]) f[now^1][j][k+1]=(f[now^1][j][k+1]+f[now][j][k])%mod;

            if(a[i+1]==b[i+j+1-k]) f[now^1][j][k]=(f[now^1][j][k]+f[now][j][k])%mod;

            if(b[j+1]==a[k+1]) f[now][j+1][k+1]=(f[now][j+1][k+1]+f[now][j][k])%mod;

            if(b[j+1]==b[i+j+1-k]) f[now][j+1][k]=(f[now][j+1][k]+f[now][j][k])%mod;

        }

       now^=1;

    } 

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

    return 0;

}