一开始最不好想：答案同时可以表示为两个人分别干这个事情，如果a得到的序列=b得到的序列，那么ans++。
于是我们就可以dp[i][j][k]表示共取出了i个，a在第一根管子里取出j个，b取出k个。
这样的复杂度是n^3，不足以通过本题。
打表发现真正需要的状态很少，于是先bfs出所有的状态，然后for一遍状态即可。
（常数比较大。。。。。）
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> #define maxn 505 #define maxm 5000050 #define mod 1024523 using namespace std; int n,m,tot=0,dp[maxm]; char s1[maxn],s2[maxn]; struct status { int x,y,z; status (int x,int y,int z):x(x),y(y),z(z) {} status () {} friend bool operator < (const status &x,const status &y) { if (x.x!=y.x) return x.x<y.x; if (x.y!=y.y) return x.y<y.y; return x.z<y.z; } }p[maxm]; map <status,int> mp; queue <status> q; void bfs() { status ret=status(0,0,0);p[1]=ret; mp[ret]=++tot;q.push(ret); while (!q.empty()) { status head=q.front();q.pop(); int x=head.x,y=head.y,z=head.z; if (s2[m-x+y]==s2[m-x+z] && y<=n && z<=n && x-y<m && x-z<m) { status ret=status(x+1,y,z); if (!mp[ret]) {mp[ret]=++tot;p[tot]=ret;q.push(ret);} } if (s1[n-y]==s2[m-x+z] && y<n && z<=n && x-y<=m && x-z<m) { status ret=status(x+1,y+1,z); if (!mp[ret]) {mp[ret]=++tot;p[tot]=ret;q.push(ret);} } if (s2[m-x+y]==s1[n-z] && y<=n && z<n && x-y<m && x-z<=m) { status ret=status(x+1,y,z+1); if (!mp[ret]) {mp[ret]=++tot;p[tot]=ret;q.push(ret);} } if (s1[n-y]==s1[n-z] && y<n && z<n && x-y<=m && x-z<=m) { status ret=status(x+1,y+1,z+1); if (!mp[ret]) {mp[ret]=++tot;p[tot]=ret;q.push(ret);} } } } int main() { scanf("%d%d",&n,&m); scanf("%s",s1+1);scanf("%s",s2+1); bfs(); dp[1]=1; for (int i=2;i<=tot;i++) { int x=p[i].x,y=p[i].y,z=p[i].z; if (s1[n-y+1]==s1[n-z+1] && y && z) { status ret=status(x-1,y-1,z-1); if (mp[ret]) dp[i]=(dp[i]+dp[mp[ret]])%mod; } if (s1[n-y+1]==s2[m-x+z+1] && y) { status ret=status(x-1,y-1,z); if (mp[ret]) dp[i]=(dp[i]+dp[mp[ret]])%mod; } if (s2[m-x+y+1]==s1[n-z+1] && z) { status ret=status(x-1,y,z-1); if (mp[ret]) dp[i]=(dp[i]+dp[mp[ret]])%mod; } if (s2[m-x+y+1]==s2[m-x+z+1]) { status ret=status(x-1,y,z); if (mp[ret]) dp[i]=(dp[i]+dp[mp[ret]])%mod; } } printf("%d ",dp[mp[status(n+m,n,n)]]); return 0; }