[xsy3343]程序锁

题意：有两个序列，序列中数字$\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<stdio.h>
#include<string.h>
#include<algorithm>
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);
}

巴特西

[xsy3343]程序锁

最新文章

热门文章