[NOI2009]管道取珠（DP）

Luogu1758

DarkBZOJ1566

题解

因为他要让我们求出每种状态出现次数的平方和,这样模拟两人取球的时候,设第一个人取球的方案为A,第二个人取球的方案为B,

这样对于每一个A，都有C(n + m , n)种B的方案与之对应,所以这样求出来正好是每种状态出现次数的平方和

所以方案数的平方和转化为选两次结果一样的方案数

我们用f[i][j][k][l]表示两个人同时取出了i+j个球,第一个人第1行取了i个球，第二行取了j个球,第二个人第1行取了k个球，第二行取了l个球

省掉一维,再用滚动数组

/*

f[i][j][k]表示第1种方案第一行选了i个，第二行选了j个

第二种方案第一行选了k个，第二行选了i+j-k个

*/

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

const int M = 505 ;

const int mod = 1024523 ;

using namespace std ;

inline int read() {

    char c = getchar() ; int x = 0 , w = 1 ;

    while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }

    while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }

    return x*w ;

}

int n , m ;

int f[2][M][M] , cur ;

char up[M] , dw[M] ;

int main() {

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

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

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

    for(int i = 0 , l ; i <= n ; i ++ , cur ^= 1)

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

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

                if(f[cur][j][k] == 0) continue ;

                l = i + j - k ;

                if(up[i + 1] == up[k + 1])

                    f[cur ^ 1][j][k + 1] = (f[cur ^ 1][j][k + 1] + f[cur][j][k])%mod ;

                if(up[i + 1] == dw[l + 1])

                    f[cur ^ 1][j][k] = (f[cur ^ 1][j][k] + f[cur][j][k])%mod ;

                if(dw[j + 1] == up[k + 1])

                    f[cur][j + 1][k + 1] = (f[cur][j + 1][k + 1] + f[cur][j][k])%mod ;

                if(dw[j + 1] == dw[l + 1])

                    f[cur][j + 1][k] = (f[cur][j + 1][k] + f[cur][j][k])%mod ;

                f[cur][j][k] = 0 ;//卡常技巧,滚动数组时直接清0,避免memset

            }

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

    return 0 ;

}