[NOI2009]管道取珠

计数dp

题意：给你两根单口开的管道，每个管道里有两种小球，管子内的小球个数分别为n,m。每次从一个管子里取出一个小球，依此排放组成一个序列，求不同取球序列的方案数的平方和(数据范围n,m<=500）

题解：平方和可以转换为有两个人小A和小B取球，如果小B和小A的取法相同，则对这种情况+1，假设该种取法有x种，那么这种序列就会被+x*x，也就是我们所需要的平方和，然后再用dp的思想处理一下就可以得到我们想要的答案。需要用到三维dp，第一维表示取球总数，第二维表示小A取第一根管的球数，第三维表示小B取第一根管的球数。又由于空间的限制，所以我们可以用滚动数组来代替掉第一维。

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=500+2;
const int mod=1024523;
int dp[2][maxn][maxn];

char sa[maxn],sb[maxn];
int a[maxn],b[maxn];

int main()
{
    int n,m;scanf("%d%d",&n,&m);
    scanf("%s%s",&sa,&sb);
    for(int i=n-1;i>=0;i--) a[n-i]=sa[i]=='A'?0:1;
    for(int i=m-1;i>=0;i--) b[m-i]=sb[i]=='A'?0:1;
    dp[0][0][0]=1;
    for(int i=0;i<=n+m;i++)
    {
        int la=i&1;
        int now=la^1;
        for(int j=0;j<=n;j++) for(int k=0;k<=n;k++) dp[now][j][k]=0;
        for(int j=0;j<=n;j++)
        {

            for(int k=0;k<=n;k++)
            {
                int j_x=i-j,k_x=i-k,cnt=dp[la][j][k];
                if(a[j+1]==a[k+1]) dp[now][j+1][k+1]=(dp[now][j+1][k+1]+cnt)%mod;
                if(a[j+1]==b[k_x+1]) dp[now][j+1][k]=(dp[now][j+1][k]+cnt)%mod;
                if(b[j_x+1]==a[k+1]) dp[now][j][k+1]=(dp[now][j][k+1]+cnt)%mod;
                if(b[j_x+1]==b[k_x+1]) dp[now][j][k]=(dp[now][j][k]+cnt)%mod;

            }

        }
    }
    printf("%d\n",dp[(n+m)&1][n][n]);
}