文章Educational Codeforces Round 106 (Rated for Div. 2) | CF1499，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

E

一个暴力是显然的，\(f(i,j,k)\) 表示当前已经使用 \(a\) 的前 \(i\) 位，\(b\) 的前 \(j\) 位，最后一位是 \(a\) 还是 \(b\) 的。然后 \(O(n^2)\) 枚举起点跑下去即可。为啥这个是对的呢？考虑每次转移都是加 \(1/0\)，显然之后在约束之下的转移本质不同。

第一眼我的想法是从如何对 \(2\) 个整串入手，手玩了一下过程，显然考虑增量法构造，然后在写了这个 \(dp\) 后再证了正确性。由此可见先猜想后证明的重要性。但其实这个 dp 的状态设计是很显然的，考虑 \(LCS\) 的那个 \(dp\) 不难想到。抑或是通过增量法，从上一个状态的本质不同加以限制转移到当前状态的本质不同。值得学习！

但我们发现，起点仅仅只是关系到初始值，但期间的转移是固定的。也就是说，对于 \(f(r,R)\) 它的起点可能很多，但是 \(f(r,R)\to f(r+1,R) \ or \ f(r,R+1)\) 的是否可以转移都是不被起点的选择所影响的。于是，不难类矩阵加速的图论意义一样（限制转移多少次）类比到图上，发现即是一个多源的 DAG 拓扑问题，然后对 \(2\) 个串都不能为空多加一维限制即可。然后就做完了。

在 debug 中可能会出现非超级源点所连的链的末尾是 \(T\)，虽然起点不能从超源获取权值，但是也需要跑，因为其间的点可能有权值，不然会影响 \(T\) 的答案转移。

注意有点卡常，于是不能像其他 \(dp\) 做法一样使用 \([1,3]\) 来限定是否某方为空串，发现永远不会有末尾是 \(T\) 但状态中表示只选 \(S\) 的情况，于是只是用 \([0,1]\)，表示当前是否只选择了当前末尾的这一类（即不是末尾的那个字符串选的是个空串）即可。

998244353 莫 #define int long long

#include #define pb push_back#define ADD(x,y) ((x+y>=mod)?x+y-mod:x+y)using namespace std;const int N=1002,mod=998244353;bool bs;char s[N],t[N];int n,m,ans,S,T,tot,id[N][N][2][2];int v[N*N*2*2],du[N*N*2*2];queueq;vectorg[N*N*2*2];bool bt;void solve() {q.push(S); v[S]=1;for(int i=2;i<=tot;i++) if(!du[i]) q.push(i); while(!q.empty()) {int x=q.front(); q.pop();//if(x==T) //cout<>s+1>>t+1;n=strlen(s+1); m=strlen(t+1);S=++tot;for(int i=0;i<=n;i++) {for(int j=0;j<=m;j++) {for(int k=0;k<=1;k++) {for(int kk=0;kk<=1;kk++) {id[i][j][k][kk]=++tot;}}if(i>=1) {g[S].pb(id[i][j][0][0]);++du[id[i][j][0][0]];}if(j>=1) {g[S].pb(id[i][j][1][0]);++du[id[i][j][1][0]];}}}T=++tot;for(int i=0;i<=n;i++) {for(int j=0;j<=m;j++) {//if(i>=1) {//g[id[i][j][0][2]].pb(T);//++du[T];//}if(i>=1&&j>=1) {g[id[i][j][0][1]].pb(T);++du[T];g[id[i][j][1][1]].pb(T);++du[T];}}}for(int i=0;i<=n;i++) {for(int j=0;j<=m;j++) {if(i>=1) {if(i+1<=n&&s[i]!=s[i+1]) {//for(int k=1;k<=3;k++) {//if(k==2) continue ;//g[id[i][j][0][k]].pb(id[i+1][j][0][k|1]);//++du[id[i+1][j][0][k|1]];//}g[id[i][j][0][0]].pb(id[i+1][j][0][0]);++du[id[i+1][j][0][0]];if(j>=1) {g[id[i][j][0][1]].pb(id[i+1][j][0][1]);++du[id[i+1][j][0][1]];}}if(j+1<=m&&s[i]!=t[j+1]) {//for(int k=1;k<=3;k++) {//if(k==2) continue ;//g[id[i][j][0][k]].pb(id[i][j+1][1][k|2]);//++du[id[i][j+1][1][k|2]];//}g[id[i][j][0][0]].pb(id[i][j+1][1][1]);++du[id[i][j+1][1][1]];if(j>=1) {g[id[i][j][0][1]].pb(id[i][j+1][1][1]);++du[id[i][j+1][1][1]];}}}if(j>=1) {if(i+1<=n&&t[j]!=s[i+1]) {//for(int k=2;k<=3;k++) {//g[id[i][j][1][k]].pb(id[i+1][j][0][k|1]);//++du[id[i+1][j][0][k|1]];//}g[id[i][j][1][0]].pb(id[i+1][j][0][1]);++du[id[i+1][j][0][1]];if(i>=1) {g[id[i][j][1][1]].pb(id[i+1][j][0][1]);++du[id[i+1][j][0][1]];}}if(j+1<=m&&t[j]!=t[j+1]) {//for(int k=2;k<=3;k++) {//g[id[i][j][1][k]].pb(id[i][j+1][1][k|2]);//++du[id[i][j+1][1][k|2]];//}g[id[i][j][1][0]].pb(id[i][j+1][1][0]);++du[id[i][j+1][1][0]];if(i>=1) {g[id[i][j][1][1]].pb(id[i][j+1][1][1]);++du[id[i][j+1][1][1]];}}}}}//cout<