上海建设银行网站,长沙房产政务信息网,wordpress前台注册登入,中国500强排行榜宝藏
首先#xff0c;这个问题等价于给定两个字符串S,T #xff0c;每次询问LCS(S[1,n],T[x,y])LCS(S[1,n],T[x,y])LCS(S[1,n],T[x,y])。 对每个询问重新求一遍LCSLCSLCS显然不现实#xff0c;又因为yyy都是连续变化的#xff0c;我们考虑探讨 LCS(S[1,n],T[x,y])与LCS(S[…宝藏
首先这个问题等价于给定两个字符串S,T 每次询问LCS(S[1,n],T[x,y])LCS(S[1,n],T[x,y])LCS(S[1,n],T[x,y])。 对每个询问重新求一遍LCSLCSLCS显然不现实又因为yyy都是连续变化的我们考虑探讨 LCS(S[1,n],T[x,y])与LCS(S[1,n],T[x,y−1])的关系\color{Red}{LCS(S[1,n],T[x,y])与LCS(S[1,n],T[x,y-1])的关系}LCS(S[1,n],T[x,y])与LCS(S[1,n],T[x,y−1])的关系
其实很明显LCS(S[1,n],T[x,y])LCS(S[1,n],T[x,y−1])或LCS(S[1,n],T[x,y−1])1LCS(S[1,n],T[x,y])LCS(S[1,n],T[x,y-1])或LCS(S[1,n],T[x,y-1])1LCS(S[1,n],T[x,y])LCS(S[1,n],T[x,y−1])或LCS(S[1,n],T[x,y−1])1 相等的情况可以不用管我们只要关注什么情况下加上yyy后匹配数会1
设一个大写字母代表定义一个字符串一个小写字母代表定义一个字符
引理 所有满足LCS(S,Py)LCS(S,P)1LCS(S,Py)LCS(S,P)1LCS(S,Py)LCS(S,P)1的位置构成T的一个后缀 证明 若LCS(S,Py)LCS(S,P)1LCS(S,Py)LCS(S,P)1LCS(S,Py)LCS(S,P)1 则LCS(S,Gy)LCS(S,G)1LCS(S,Gy)LCS(S,G)1LCS(S,Gy)LCS(S,G)1(GGG为PPP的后缀) 即SSS中至少有一个yyy是PPP匹配不到的 那GGG也是匹配不到这个yyy的所以多加一个yyy一定会让匹配数1
也就是说假设iii是满足LCS(S,T[i,y])LCS(S,T[i,y−1])1LCS(S,T[i,y])LCS(S,T[i,y-1])1LCS(S,T[i,y])LCS(S,T[i,y−1])1的位置中最靠前的那么 ∀ji满足LCS(S,T[j,y])LCS(S,T[j,y−1])1\forall ji满足LCS(S,T[j,y])LCS(S,T[j,y-1])1∀ji满足LCS(S,T[j,y])LCS(S,T[j,y−1])1 也就是说只要我们找到这个位置最靠前的iii便能找到所有jjj
现在就可以考虑 dp 了。设f(i,j)f(i,j)f(i,j)表示考虑了SSS长度为iii的前缀、TTT长度为jjj的前缀T[1,j]T[1,j]T[1,j] 最长的后缀PyPyPy满足LCS(S[1,i],Py)LCS(S[1,i],P)1LCS(S[1,i],Py)LCS(S[1,i],P)1LCS(S[1,i],Py)LCS(S[1,i],P)1。f(i,j)f(i,j)f(i,j)表示PyPyPy的起始位置。
考虑f(i,j)f(i,j)f(i,j)的转移 先把LCSLCSLCS的转移式打出来 LCSi,j{LCSi−1,j−11(S[i]T[j])max{LCSi−1,j,LCSi,j−1}(S[i]!T[j])LCS_{i,j}\left\{ \begin{aligned} LCS_{i-1,j-1}1(S[i]T[j]) \\ max\{LCS_{i-1,j},LCS_{i,j-1}\} (S[i]!T[j])\\ \end{aligned} \right. LCSi,j{LCSi−1,j−11(S[i]T[j])max{LCSi−1,j,LCSi,j−1}(S[i]!T[j]) 若S[i]yS[i]yS[i]y 则根据LCSLCSLCS的转移式 LCS(S[1,i],Py)LCS(S[1,i−1],P)1LCS(S[1,i],Py)LCS(S[1,i-1],P)1LCS(S[1,i],Py)LCS(S[1,i−1],P)1 又∵LCS(S[1,i],Py)LCS(S[1,i],P)1\because LCS(S[1,i],Py)LCS(S[1,i],P)1∵LCS(S[1,i],Py)LCS(S[1,i],P)1 ∴LCS(S[1,i−1],P)LCS(S[1,i],P)\therefore LCS(S[1,i-1],P)LCS(S[1,i],P)∴LCS(S[1,i−1],P)LCS(S[1,i],P) ∴LCS(S[1,i],Py)LCS(S[1,i],P)1⇒LCS(S[1,i−1],P)LCS(S[1,i],P)\therefore LCS(S[1,i],Py)LCS(S[1,i],P)1\Rightarrow LCS(S[1,i-1],P)LCS(S[1,i],P)∴LCS(S[1,i],Py)LCS(S[1,i],P)1⇒LCS(S[1,i−1],P)LCS(S[1,i],P)
我们不妨新设一个状态g(i,j)g(i,j)g(i,j)表示在T[1,j]T[1,j]T[1,j]里找最长的后缀QQQ满足LCS(S[1,i−1],T[1,j])LCS(S[1,i],T[1,j])LCS(S[1,i-1],T[1,j])LCS(S[1,i],T[1,j])LCS(S[1,i−1],T[1,j])LCS(S[1,i],T[1,j])g(i,j)g(i,j)g(i,j)表示QQQ的起点位置
∴f(i,j)g(i,j−1)\therefore f(i,j)g(i,j-1)∴f(i,j)g(i,j−1)
若S[i]!yS[i]!yS[i]!y 则根据LCSLCSLCS的转移式 LCS(S[1,i],Py)max{LCS(S[1,i−1],Py),LCS(S[1,i],P)}LCS(S[1,i],Py)max\{LCS(S[1,i-1],Py),LCS(S[1,i],P)\}LCS(S[1,i],Py)max{LCS(S[1,i−1],Py),LCS(S[1,i],P)} 又∵LCS(S[1,i],Py)LCS(S[1,i],P)1\because LCS(S[1,i],Py)LCS(S[1,i],P)1∵LCS(S[1,i],Py)LCS(S[1,i],P)1 ∴LCS(S[1,i−1],Py)LCS(S[1,i],P)1\therefore LCS(S[1,i-1],Py)LCS(S[1,i],P)1∴LCS(S[1,i−1],Py)LCS(S[1,i],P)1 若LCS(S[1,i],P)LCS(S[1,i−1],P)1LCS(S[1,i],P)LCS(S[1,i-1],P)1LCS(S[1,i],P)LCS(S[1,i−1],P)1 则LCS(S[1,i−1],Py)LCS(S[1,i−1],P)2(舍)LCS(S[1,i-1],Py)LCS(S[1,i-1],P)2(舍)LCS(S[1,i−1],Py)LCS(S[1,i−1],P)2(舍) ∴LCS(S[1,i],P)LCS(S[1,i−1],P)\therefore LCS(S[1,i],P)LCS(S[1,i-1],P)∴LCS(S[1,i],P)LCS(S[1,i−1],P) ∴LCS(S[1,i],Py)LCS(S[1,i],P)1⇒{LCS(S[1,i],P)LCS(S[1,i−1],P)LCS(S[1,i−1],Py)LCS(S[1,i−1],P)1\therefore LCS(S[1,i],Py)LCS(S[1,i],P)1\Rightarrow \left\{ \begin{aligned} LCS(S[1,i],P)LCS(S[1,i-1],P) \\ LCS(S[1,i-1],Py)LCS(S[1,i-1],P)1\\ \end{aligned} \right. ∴LCS(S[1,i],Py)LCS(S[1,i],P)1⇒{LCS(S[1,i],P)LCS(S[1,i−1],P)LCS(S[1,i−1],Py)LCS(S[1,i−1],P)1 ∴f(i,j)max{f(i−1,j),g(i,j−1)}\therefore f(i,j)max\{f(i −1,j),g(i,j−1)\}∴f(i,j)max{f(i−1,j),g(i,j−1)}
再考虑g(i,j)g(i,j)g(i,j)的转移 设QPyQPyQPy 若S[i]yS[i]yS[i]y 则根据LCSLCSLCS的转移式 LCS(S[1,i],Py)LCS(S[1,i−1],P)1LCS(S[1,i],Py)LCS(S[1,i-1],P)1LCS(S[1,i],Py)LCS(S[1,i−1],P)1 又∵LCS(S[1,i−1],Py)LCS(S[1,i],Py)\because LCS(S[1,i-1],Py)LCS(S[1,i],Py)∵LCS(S[1,i−1],Py)LCS(S[1,i],Py) ∴LCS(S[1,i−1],Py)LCS(S[1,i−1],P)1\therefore LCS(S[1,i-1],Py)LCS(S[1,i-1],P)1∴LCS(S[1,i−1],Py)LCS(S[1,i−1],P)1 ∴LCS(S[1,i−1],Py)LCS(S[1,i],Py)⇒\therefore LCS(S[1,i-1],Py)LCS(S[1,i],Py)\Rightarrow∴LCS(S[1,i−1],Py)LCS(S[1,i],Py)⇒ LCS(S[1,i−1],Py)LCS(S[1,i−1],P)1LCS(S[1,i-1],Py)LCS(S[1,i-1],P)1LCS(S[1,i−1],Py)LCS(S[1,i−1],P)1 ∴g(i,j)f(i−1,j)\therefore g(i,j) f(i−1,j)∴g(i,j)f(i−1,j)
若S[i]!yS[i]!yS[i]!y 引理 LCS(Ax,By)LCS(A,B)1LCS(Ax,By)LCS(A,B)1LCS(Ax,By)LCS(A,B)1 证明 若xyxyxy LCS(Ax,By)LCS(A,B)1LCS(Ax,By)LCS(A,B)1LCS(Ax,By)LCS(A,B)1引理显然成立 若x!yx!yx!y ∵{LCS(A,By)LCS(A,B)1LCS(Ax,By)LCS(A,B)1\because \left\{ \begin{aligned} LCS(A,By)LCS(A,B)1 \\ LCS(Ax,By)LCS(A,B)1\\ \end{aligned} \right. ∵{LCS(A,By)LCS(A,B)1LCS(Ax,By)LCS(A,B)1 ∴LCS(Ax,By)max{LCS(A,By),LCS(Ax,B)}LCS(A,B)1\therefore LCS(Ax,By)max\{LCS(A,By),LCS(Ax,B)\}LCS(A,B)1∴LCS(Ax,By)max{LCS(A,By),LCS(Ax,B)}LCS(A,B)1
根据LCSLCSLCS的转移式 LCS(S[1,i],Py)max{LCS(S[1,i−1],Py),LCS(S[1,i],P)}LCS(S[1,i],Py)max\{LCS(S[1,i-1],Py),LCS(S[1,i],P)\}LCS(S[1,i],Py)max{LCS(S[1,i−1],Py),LCS(S[1,i],P)}
若LCS(S[1,i−1],Py)LCS(S[1,i−1],P)LCS(S[1,i-1],Py)LCS(S[1,i-1],P)LCS(S[1,i−1],Py)LCS(S[1,i−1],P) 则LCS(S[1,i],P)LCS(S[1,i−1],P)LCS(S[1,i],P)LCS(S[1,i-1],P)LCS(S[1,i],P)LCS(S[1,i−1],P)
若LCS(S[1,i−1],Py)LCS(S[1,i−1],P)1LCS(S[1,i-1],Py)LCS(S[1,i-1],P)1LCS(S[1,i−1],Py)LCS(S[1,i−1],P)1 则根据引理LCS(S[1,i],Py)LCS(S[1,i−1],P)1LCS(S[1,i],Py)LCS(S[1,i-1],P)1LCS(S[1,i],Py)LCS(S[1,i−1],P)1 ∴LCS(S[1,i−1],Py)LCS(S[1,i],Py)必成立\therefore LCS(S[1,i-1],Py)LCS(S[1,i],Py)必成立∴LCS(S[1,i−1],Py)LCS(S[1,i],Py)必成立
∴LCS(S[1,i−1],Py)LCS(S[1,i],Py)⇒\therefore LCS(S[1,i-1],Py)LCS(S[1,i],Py)\Rightarrow∴LCS(S[1,i−1],Py)LCS(S[1,i],Py)⇒ LCS(S[1,i],P)LCS(S[1,i−1],P)或LCS(S[1,i−1],Py)LCS(S[1,i−1],P)1LCS(S[1,i],P)LCS(S[1,i-1],P)或LCS(S[1,i-1],Py)LCS(S[1,i-1],P)1LCS(S[1,i],P)LCS(S[1,i−1],P)或LCS(S[1,i−1],Py)LCS(S[1,i−1],P)1 ∴g(i,j)min{f(i−1,j),g(i,j−1)}\therefore g(i, j) min\{f(i−1, j), g(i,j−1)\}∴g(i,j)min{f(i−1,j),g(i,j−1)}
#includeiostream
#includecstdio
#includealgorithm
using namespace std;
typedef long long ll;
const int N5005;
const ll mod998244353;
int n,m,s[N],t[N];
int f[N][N],g[N][N],c[N];
ll p[N],ans[N];
int main(){scanf(%d%d,n,m);p[0]1;for(int i1;im;i) p[i]p[i-1]*233%mod;for(int i1;in;i) scanf(%d,s[i]);for(int i1;im;i) scanf(%d,t[i]);for(int i0;im;i) f[0][i]i1;for(int i1;in;i){for(int j1;jm;j){if(s[i]t[j]){f[i][j]g[i][j-1];g[i][j]f[i-1][j];}else{f[i][j]max(f[i-1][j],g[i][j-1]);g[i][j]min(f[i-1][j],g[i][j-1]);}} }for(int i1;im;i){for(int jf[n][i];ji;j) c[j];for(int j1;ji;j) ans[j](ans[j]c[j]*p[i-j]%mod)%mod;}for(int i1;im;i) printf(%lld\n,ans[i]);return 0;
}
