题意：有两个序列，序列中数字$\in\{-1,0,1\}$

有两个指针，初始时分别指向两个序列的开始位置，有一个初始为$0$的数$a$，重复以下过程直到两个指针都指向序列末尾后

如果一个指针指向末尾后，那么移动另一个指针

否则如果$a>0$，随机移动一个指针

否则如果至少一个指针指向$1$，随机移动一个指向$1$的指针

否则随机移动一个指针

每移动一个指针，就把这个指针指向的数加到$a$上

问有多少种填$0$为$\pm1$的方法使得任何时候都有$a\geq0$

 

首先是对填好的序列进行判定，在两个序列中分别找到以$-1$结尾的最小前缀和$s_a,s_b$（如果序列全为$1$就选择总和），如果两个序列都满足这个最小前缀和$\ne$总和，那么条件是$s_a+s_b\geq-1$（因为两个$-1$后面一定都紧跟着一个$1$，而后面的前缀和不会更小，所以可以满足），否则需要满足$s_a+s_b\geq0$（一个序列的指针已经到了末尾后，只能被强迫移动另一个指针）

现在要DP，正着DP很困难，考虑倒着DP，这样每次只会增加一个小前缀

设$f_{i,j,k}$表示填完$[i,n]$，这些位置相对于$i$的前缀和中，以$-1$结尾的最小前缀和$=j$的方案数，$k$表示$j$是否等于总和

如果$i-1$位可以填$1$，那么有$f_{i,j,0}\rightarrow f_{i-1,j+1,0},f_{i,j,1}\rightarrow f_{i-1,j+1,1}$，因为在最前面加一个$1$并不改变原来的最小前缀和

如果$i-1$位可以填$-1$，那么有$f_{i,j,0}\rightarrow f_{i-1,\min(-1,j-1),0},f_{i,j,1}\rightarrow f_{i-1,\min(-1,j-1),[j\le0]}$，因为增加了一个值为$-1$的前缀和，所以原来$j>0$且最小前缀和$=j$的方案会变为最小前缀和$=-1\ne j-1$

对两个序列分别DP后直接统计答案即可

#include
     
      #include
      
       #include
       
        using namespace std;typedef long long ll;typedef int pr[2];const int mod=998244353;int mul(int a,int b){return(ll)a*b%mod;}void inc(int&a,int b){(a+=b)>=mod?a-=mod:0;}struct str{	char s[5010];	int n;	pr _f[10010],_g[10010],*f=_f+5000,*g=_g+5000;	void work(){		int i,j;		scanf("%s",s+1);		n=strlen(s+1);		f[0][1]=1;		for(i=n;i>0;i--){			memset(_g,0,sizeof(_g));			for(j=-n;j<=n;j++){				if(s[i]!='P'){//+					inc(g[j+1][0],f[j][0]);					inc(g[j+1][1],f[j][1]);				}				if(s[i]!='V'){//-					inc(g[min(-1,j-1)][0],f[j][0]);					inc(g[min(-1,j-1)][j<=0],f[j][1]);				}			}			memcpy(_f,_g,sizeof(_g));		}	}}a,b;int main(){	int i,j,s;	a.work();	b.work();	s=0;	for(i=-a.n;i<=a.n;i++){		for(j=-b.n;j<=b.n;j++){			if(i+j>=-1)inc(s,mul(a.f[i][0],b.f[j][0]));			if(i+j>=0){				inc(s,mul(a.f[i][0],b.f[j][1]));				inc(s,mul(a.f[i][1],b.f[j][0]));				inc(s,mul(a.f[i][1],b.f[j][1]));			}		}	}	printf("%d",s);}