题有点骚。。
sum a[i]*a[i]可以理解为两个独立但同时进行的游戏得到同一个输出序列的方案数。
设f[l,i,j]为每个游戏都已经推出了l个珠子时,第一个游戏里上边儿的管道已经推出了i个,第二个游戏中上边儿管道推出了j个的方案数。
考虑到若要推出序列相同,那么对于每个阶段l,两个游戏的推出序列应始终相等。这样,跑跑计数dp就好了
#include <bits/stdc++.h> using namespace std; const int n=507; const int p=1024523; int n,m; char a[n],b[n]; int f[2][n][n]; inline void add(int&x,int y) { if((x+=y)>=p) x-=p; } int main() { scanf("%d%d%s%s",&n,&m,a+1,b+1); f[0][0][0]=1; int now=0, nxt=1; for(int l=0; l<n+m; ++l) { for(int i=0; i<=l && i<=n; ++i) { for(int j=0; j<=l && j<=n; ++j) { if(!f[now][i][j]) continue; if(a[i+1]==a[j+1]) add(f[nxt][i+1][j+1],f[now][i][j]); if(a[i+1]==b[l-j+1]) add(f[nxt][i+1][j],f[now][i][j]); if(b[l-i+1]==a[j+1]) add(f[nxt][i][j+1],f[now][i][j]); if(b[l-i+1]==b[l-j+1]) add(f[nxt][i][j],f[now][i][j]); f[now][i][j]=0; } } now=nxt, nxt^=1; } printf("%dn",f[now][n][n]); }
算是可做题吧。。。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605680.html