P1758 [NOI2009] 管道取珠 做题记录

P1758 [NOI2009] 管道取珠

方案数的平方可以看做是两个人分别操作，操作到同一种结果的方案数。

直接 dp 一下即可。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=505,p=1024523;

int n,m;
int a[S],b[S];
int dp[2][S][S];

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

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf(" %c",&a[i]),a[i]-='A';
	for(int i=1;i<=m;i++) scanf(" %c",&b[i]),b[i]-='A';
	for(int i=1;i<=n/2;i++) swap(a[i],a[n-i+1]);
	for(int i=1;i<=m/2;i++) swap(b[i],b[m-i+1]);
	dp[0][0][0]=1;
	for(int i=0;i<=n+m;i++)
	{
		int u=i&1,v=i&1^1;
		for(int j=0;j<=i-1&&j<=n;j++) for(int k=0;k<=i-1&&k<=n;k++) dp[v][j][k]=0;
		for(int j=0;j<=i&&j<=n;j++)
		{
			for(int k=0;k<=i&&k<=n;k++)
			{
				if(dp[u][j][k]==0) continue;
				int jb=i-j,kb=i-k;
				if(j<n&&k<n&&a[j+1]==a[k+1]) add(dp[v][j+1][k+1],dp[u][j][k]);
				if(jb<m&&k<n&&b[jb+1]==a[k+1]) add(dp[v][j][k+1],dp[u][j][k]);
				if(j<n&&kb<m&&a[j+1]==b[kb+1]) add(dp[v][j+1][k],dp[u][j][k]);
				if(jb<m&&kb<m&&b[jb+1]==b[kb+1]) add(dp[v][j][k],dp[u][j][k]);
			}
		}
	}
	printf("%d\n",dp[n+m&1][n][n]);
	return 0;
}