[洛谷 1758][NOI2009]管道取珠

题目链接

https://www.luogu.com.cn/problem/P1758

题解

转化问题：一种序列有 \(a_i\) 种产生方式，因此 \(\sum a_i^2\) 可以认为是两次产生同一序列的方案数。

设 \(f_{k,i,j}\) 表示两个人一共取了 \(k\) 个球，第一个人从上面取了 \(i\) 个球，第二个人从上面取 \(j\) 个球，产生同一序列的方案数。

转移时枚举两个人从上面或是从下面取，只有当取的球一样时才能转移。

时间复杂度 \(O(n^3)\)。

#include <iostream>
#include <algorithm>
#define MOD 1024523
using namespace std;
int f[2][505][505];
char s[505],t[505];
int a[505],b[505];
int main()
{
 int n,m;
 cin>>n>>m;
 cin>>(s+1);
 cin>>(t+1);
 for(int i=1;i<=n;i++)
  a[i]=(s[n-i+1]=='A');
 for(int i=1;i<=m;i++)
  b[i]=(t[m-i+1]=='A');
 f[0][0][0]=1;
 for(int k=1;k<=n+m;k++)
 {
  int p=k&1,q=p^1;
  for(int i=0;i<=n;i++)
   for(int j=0;j<=n;j++)
    f[p][i][j]=0;
  for(int i=max(k-m,0);i<=min(n,k);i++)
   for(int j=max(k-m,0);j<=min(n,k);j++)
   {
    if(i&&j&&a[i]==a[j])
     f[p][i][j]=(f[p][i][j]+f[q][i-1][j-1])%MOD;
    if(i&&k-j&&a[i]==b[k-j])
     f[p][i][j]=(f[p][i][j]+f[q][i-1][j])%MOD;
    if(j&&k-i&&a[j]==b[k-i])
     f[p][i][j]=(f[p][i][j]+f[q][i][j-1])%MOD;
    if(k-j&&k-i&&b[k-j]==b[k-i])
     f[p][i][j]=(f[p][i][j]+f[q][i][j])%MOD;
   }
 }
 cout<<f[(n+m)&1][n][n]<<endl;
 return 0;
}