[NOI2009] 管道取珠

题有点骚。。

sum a[i]*a[i]可以理解为两个独立但同时进行的游戏得到同一个输出序列的方案数。

设f[l,i,j]为每个游戏都已经推出了l个珠子时，第一个游戏里上边儿的管道已经推出了i个，第二个游戏中上边儿管道推出了j个的方案数。

考虑到若要推出序列相同，那么对于每个阶段l，两个游戏的推出序列应始终相等。这样，跑跑计数dp就好了

#include <bits/stdc++.h>
using namespace std;
const int N=507;
const int P=1024523;

int n,m;
char a[N],b[N];
int f[2][N][N];

inline void add(int&x,int y) {
    if((x+=y)>=P) x-=P;
}

int main() {
    scanf("%d%d%s%s",&n,&m,a+1,b+1);
    f[0][0][0]=1;
    int now=0, nxt=1;
    for(int l=0; l<n+m; ++l) {
        for(int i=0; i<=l && i<=n; ++i) {
            for(int j=0; j<=l && j<=n; ++j) {
                if(!f[now][i][j]) continue;
                if(a[i+1]==a[j+1]) add(f[nxt][i+1][j+1],f[now][i][j]);
                if(a[i+1]==b[l-j+1]) add(f[nxt][i+1][j],f[now][i][j]);
                if(b[l-i+1]==a[j+1]) add(f[nxt][i][j+1],f[now][i][j]);
                if(b[l-i+1]==b[l-j+1]) add(f[nxt][i][j],f[now][i][j]);
                f[now][i][j]=0;
            }
        }
        now=nxt, nxt^=1;
    }
    printf("%d\n",f[now][n][n]);
}

算是可做题吧。。。

[NOI2009] 管道取珠

原文：https://www.cnblogs.com/nosta/p/10214648.html