题目概述

有两个管道，第一个有 $n$ 个黑白珠子，第二个有 $m$ 个黑白珠子，每次可以从一个管道取出最靠管道口的珠子。假设有 $k$ 中取珠子的方法，第 $i$ 种方案的方案数为 $a_i$ 那么贡献为 $\sum_{i=1}^{k}a_i^2$ 。求贡献。

解题报告

开平方可以理解为每种方案都和相同的方案有贡献，所以我们可以认为有两个取珠游戏同时进行，且只有两个游戏取出来的方案一样时才有贡献，也就是说：

定义 $f[i][j][k][t]$ 表示第一个游戏的第一个管道取了 $i$ 个，第二个管道取了 $j$ 个；第二个游戏的第一个管道取了 $k$ 个，第二个管道取了 $t$ 个的贡献，那么就只有当每次取出来的珠子颜色相同才能转移，就变成了很简单的DP。

实际上因为 $i+j=k+t$ ，所以只需要 $f[i][j][k]$ 就行了。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
const int maxn=500,MOD=1024523;

int n,m,a[maxn+5],b[maxn+5];
int f[maxn+5][maxn+5][maxn+5];

inline char getupr() {char ch=getchar();while (!isupper(ch)) ch=getchar();return ch;}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=n;i;i--) a[i]=getupr()-'A';
    for (int i=m;i;i--) b[i]=getupr()-'A';
    f[0][0][0]=1;
    for (int i=0;i<=n;i++)
        for (int j=0;j<=m;j++)
            for (int k=0,t=i+j;k<=i+j&&k<=n;k++,t--){
                int &F=f[i][j][k];
                if (i&&t&&a[i]==b[t]) AMOD(F,f[i-1][j][k]);
                if (i&&k&&a[i]==a[k]) AMOD(F,f[i-1][j][k-1]);
                if (j&&t&&b[j]==b[t]) AMOD(F,f[i][j-1][k]);
                if (j&&k&&b[j]==a[k]) AMOD(F,f[i][j-1][k-1]);
            }
    return printf("%d\n",f[n][m][n]),0;
}