题解 P1758 【管道取珠】

由于是 $∑A_i^2$ ,可以看成取两次得到了相同的串的方案数。(想一想,为什么) $f [i][j][k][l]$ 表示第一次取A串中的前 $i$ 个,取B串中的前 $j$ 个,第二次取A串中的前 $k$ 个,B串中的前 $l$ 个的方案数 因为 $k+l=i+j$ 最后一维可以省了 转移方程就很好推了,见代码 然后用滚动数组就好了 注意:本站会tle,大牛分站可以ac ```cpp #include<bits/stdc++.h> using namespace std; int read() { char s; int k=0,base=1; while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9')); if(s==EOF)exit(0); if(s=='-')base=-1,s=getchar(); while(s>='0'&&s<='9') { k=k*10+(s-'0'); s=getchar(); } return k*base; } void write(int x) { if(x<0) { putchar('-'); write(-x); } else { if(x/10)write(x/10); putchar(x%10+'0'); } } int n,m; char a[510],b[510]; int f[5][510][510],t;//滚动数组 inline void add(int A,int &B) { B+=A; if (B>1024523) B-=1024523;//取膜 } int cur=0; int main() { n=read();m=read(); scanf("%s",a+1); scanf("%s",b+1); f[0][0][0]=1; for (int i=0;i<=n;i++,cur^=1) for (int j=0;j<=m;j++) for (int k=0;k<=n;k++) { t=f[cur][j][k]; if (i+j-k>m||i+j-k<0) continue;//越界退出 if (a[i+1]==a[k+1]) add(t,f[cur^1][j][k+1]);//状态转移 if (b[j+1]==b[i+j-k+1]) add(t,f[cur][j+1][k]); if (a[i+1]==b[i+j-k+1]) add(t,f[cur^1][j][k]); if (b[j+1]==a[k+1]) add(t,f[cur][j+1][k+1]); f[cur][j][k]=0;//清掉 } printf("%d",f[cur][m][n]); return 0; } ```