33OJ
登录 注册

#ABC484G. 通配符构造

通配符构造

通配符构造

题目描述

给定由 0、1、? 组成的字符串 S,X,YS,X,Y。

称按以下过程得到的字符串为「好串」:

  1. 选择由 xx 与 yy 组成的序列 t=(t1,t2,…,tk)t=(t_1,t_2,\ldots,t_k),使得不存在整数 ii(1≤i<k1 \le i < k)满足 ti=ti+1=yt_i=t_{i+1}=y。
  2. 令 s=(s1,s2,…,sk)s=(s_1,s_2,\ldots,s_k),其中若 tit_i 为 xx 则 si=Xs_i=X,若 tit_i 为 yy 则 si=Ys_i=Y。
  3. 令 TT 为 s1,s2,…,sks_1,s_2,\ldots,s_k 依次拼接得到的字符串。
  4. 把 TT 中的每个 ? 替换为 0 或 1。

求把 SS 中的每个 ? 替换为 0 或 1 后能得到的好串个数,对 998244353998244353 取模。

输入格式

输入共三行,依次为字符串 SS、XX、YY。

输出格式

输出一行一个整数,表示好串个数对 998244353998244353 取模的结果。

?0??11?1?
0?1
?1?
5

样例 1 解释

例如取 t=(x,y,x)t=(x,y,x),则 T=T=0?1?1?0?1,把其中的 ? 适当替换后可以得到 001111011,因此 001111011 是好串。

除此之外,001011010、001011011、001011110、001011111 这四个串也满足条件,因此答案为 55。

0?10?1?01?
???
?????
0

样例 2 解释

注意 tt 中不能出现连续的 yy。

????????????1???1??0??????1???????1????????1????????????????0
?0??
?
992356689

样例 3 解释

答案需要对 998244353998244353 取模。

数据范围

对于所有测试数据,保证:

  • S,X,YS,X,Y 均由 0、1、? 组成;
  • 1≤∣S∣≤20001 \le |S| \le 2000;
  • 1≤∣X∣≤81 \le |X| \le 8,1≤∣Y∣≤81 \le |Y| \le 8;
  • 所有输入值均为整数。

子任务

本题共 20 个测试点,按测试点计分:

测试点 分值 每个测试点 特殊性质
1∼61 \sim 6 3030 55 ∣S∣≤100\vert S\vert \le 100
7∼127 \sim 12 ∣S∣≤1000\vert S\vert \le 1000
13∼2013 \sim 20 4040 无特殊限制

每个测试点单独评分,全部测试点的得分之和即为本题得分。