做题记录整理dp9 P1758 [NOI2009] 管道取珠（2022/9/23）

P1758 [NOI2009] 管道取珠
这道题的难点就在于赋予ai的平方和一个具体的含义，
我们可以想到（其实要不是上课听了根本想不到）ai的平方和其实就是两个管道取珠游戏一起玩，然后取出的序列相同的方案数，因为对于第一个人第i种序列有ai种取法，对于第二个人同理，所以两个人取出的序列相同的方案数就有ai*ai种

#include<bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
int n,m,dp[2][605][605];
string s1,s2;
const int md=1024523;
int main(){
	scanf("%d%d\n",&n,&m);
	cin>>s1;
	cin>>s2;
	s1.insert(0," ");
	s2.insert(0," ");
	dp[0][0][0]=1;
	for1(i,0,n)
	{
		memset(dp[(i+1)%2],0,sizeof(dp[(i+1)%2]));
		for1(j,0,m)
			for1(k,0,i+j)
			{
				int l=i+j-k;
				if(s1[i+1]==s1[k+1]) dp[(i+1)%2][j][k+1]=(dp[(i+1)%2][j][k+1]+dp[i%2][j][k])%md;//两个人都取上面 
				if(s1[i+1]==s2[l+1]) dp[(i+1)%2][j][k]=(dp[(i+1)%2][j][k]+=dp[i%2][j][k])%md;//第一个人取上，第二个人取下 
				if(s2[j+1]==s1[k+1]) dp[i%2][j+1][k+1]=(dp[i%2][j+1][k+1]+=dp[i%2][j][k])%md;//第一个人取下，第二个人取上 
				if(s2[j+1]==s2[l+1]) dp[i%2][j+1][k]=(dp[i%2][j+1][k]+=dp[i%2][j][k])%md;//两个人都取下面 
			}
	}
	cout<<dp[n&1][m][n];
	return 0;
}