luogu P1758 [NOI2009]管道取珠

luogu

这个题中的平方有点东西,考虑他的组合意义,也就是做这个过程两次,如果两次得到的结果一样就给答案+1,所以可以考虑dp,设\(f_{i,j,k,l}\)表示第一个过程中上面取到的第\(i\)个,下面取到第\(j\)个,第二个过程中上面取到的第\(
k\)个,下面取到第\(l\)个的答案,转移枚举两个过程分别是取上面还是下面.容易发现\(i+j=k+l\),所以可以改成\(f_{i,j,k}\)表示取了\(i\)次,第一个过程上面取到第\(j\)个,第二个过程上面取到第\(k\)个的答案

#include<bits/stdc++.h>

#define LL long long

#define uLL unsigned long long

#define db double

using namespace std;

const int N=500+10,mod=1024523;

int rd()

{

	int x=0,w=1;char ch=0;

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

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

	return x*w;

}

void ad(int &x,int y){x+=y,x-=x>=mod?mod:0;}

char cc[N],ss[N];

int n,m,f[2][N][N];

int main()

{

	n=rd(),m=rd();

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

	reverse(cc+1,cc+n+1),reverse(ss+1,ss+m+1);

	int nw=1,la=0;

	f[la][1][1]=1;

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

	{

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

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

			{

				if(!f[la][j][k]) continue;

				int jj=i+1-j,kk=i+1-k;

				if(j<=n&&k<=n&&cc[j]==cc[k]) ad(f[nw][j+1][k+1],f[la][j][k]);

				if(j<=n&&kk<=m&&cc[j]==ss[kk]) ad(f[nw][j+1][k],f[la][j][k]);

				if(jj<=m&&k<=n&&ss[jj]==cc[k]) ad(f[nw][j][k+1],f[la][j][k]);

				if(jj<=m&&kk<=m&&ss[jj]==ss[kk]) ad(f[nw][j][k],f[la][j][k]);

				f[la][j][k]=0;

			}

		nw^=1,la^=1;

	}

	printf("%d\n",f[la][n+1][n+1]);

	return 0;

}