题解

一道非常神奇的dp题。
求$a_i^2$，可以假设有甲乙两个人分别独立得从相同的管道参与，设$f[i][j][k]$表示两个人都选i个球，甲选了上面j个，乙选了上面k个，且两人产生的序列相同的方案。一个人取出一种序列有$a_i$种，两个人就会有$a_i^2$种可能。算出$f[n+m][n][n]$就是最终的答案

时间复杂度

$O((n+m)×n×m)$

C++ 代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <unordered_map>
#include <set>
#include <queue>
#define ini(a) memset(a,0,sizeof(a))
typedef long long LL;
#define Rep(i,a,n) for (int i=a;i<=n;i++)
#define Per(i,a,n) for (int i=n-1;i>=a;i--)
//#define x first
//#define y second
using namespace std;
typedef pair<LL,LL>  pll;
inline int read();
inline LL readl();
const int mod=1024523,N=510;
int f[2][N][N];
char a[N],b[N];
int main(){
    /* CODE */
    int m,n;
    scanf("%d%d",&n,&m);
    scanf("%s%s",a+1,b+1);
    reverse(a+1,a+n+1);
    reverse(b+1,b+m+1);
    f[0][0][0]=1;
    int cur=1;
    Rep(i,1,n+m){
        int l=max(0,i-m);
        int r=min(i,n);
        Rep(j,l,r){
            Rep(k,l,r){ //滚动数组
                f[cur][j][k]=0;
                if(j&&k&&a[j]==a[k])
                    f[cur][j][k]=(f[cur][j][k]+f[cur^1][j-1][k-1])%mod;
                if(j&&i-k&&a[j]==b[i-k])
                    f[cur][j][k]=(f[cur][j][k]+f[cur^1][j-1][k])%mod;
                if(i-j&&k&&b[i-j]==a[k])
                    f[cur][j][k]=(f[cur][j][k]+f[cur^1][j][k-1])%mod;
                if(i-j&&i-k&&b[i-j]==b[i-k])
                    f[cur][j][k]=(f[cur][j][k]+f[cur^1][j][k])%mod;
            }
        }
        cur^=1;
    }
    cout<<f[cur^1][n][n]<<endl;
    return 0;
}
inline int read(){
    char ch;
    while((ch=getchar())<'0'||ch>'9');
    int res=ch-48;
    while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-48;
    return res;
}
inline LL readl(){
    char ch;
    while((ch=getchar())<'0'||ch>'9');
    LL res=ch-48;
    while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-48;
    return res;
}