AT_abc484_g.Wildcard Construction
省选/NOI-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given strings S,X,Y consisting of 0, 1, and ?.
A string that can be obtained by the following procedure is called a good string.
- Choose a sequence t=(t1,t2,…,tk) consisting of x and y such that there is no integer i (1≤i<k) with ti=ti+1=y.
- Let s=(s1,s2,…,sk) be the sequence obtained by replacing each element of t with the string X if it is x, and with the string Y if it is y. Let T be the string obtained by concatenating s1,s2,…,sk in this order.
- Replace each
?in T with0or1of your choice.
Find the number, modulo 998244353, of good strings that can be obtained by replacing each ? in S with 0 or 1.
给你三个由字符 0、1 和 ? 组成的字符串 S、X、Y。
通过以下步骤可得到的字符串称为好字符串(good string):
- 选取一个由 x 和 y 构成的序列 t=(t1,t2,…,tk),满足:对任意整数 i(1≤i<k),不同时有 ti=ti+1=y。
- 将 t 中每个元素替换为字符串:若为 x,则替换为 X;若为 y,则替换为 Y,从而得到序列 s=(s1,s2,…,sk)。将 s1,s2,…,sk 按顺序拼接,得到字符串 T。
- 将 T 中每个
?替换为你选定的0或1。
求:将 S 中每个 ? 替换为 0 或 1 所能得到的所有字符串中,有多少个是好字符串?答案对 998244353 取模。
输入格式
The input is given from Standard Input in the following format:
S
X
Y
输入从标准输入中按以下格式给出:
S
X
Y
输出格式
Print the answer.
输出答案。
输入输出样例
输入#1
?0??11?1? 0?1 ?1?
输出#1
5
输入#2
0?10?1?01? ??? ?????
输出#2
0
输入#3
????????????1???1??0??????1???????1????????1????????????????0 ?0?? ?
输出#3
992356689
说明/提示
Sample 1 Explanation:
For example, the string 001111011, which can be obtained by replacing each ? in S with 0 or 1, is a good string. Starting the procedure with t=(x,y,x) gives T=0?1?1?0?1. By replacing each ? in T with 0 or 1, we can obtain 001111011, so 001111011 is a good string.
Besides this, the four strings 001011010, 001011011, 001011110, 001011111 satisfy the condition. No other strings satisfy the condition, so print 5.
Sample 2 Explanation:
Note that y must not appear consecutively in t.
Sample 3 Explanation:
Note that you should print the number of strings satisfying the condition modulo 998244353.
Constraints
- S,X,Y are strings consisting of
0,1, and?. - 1≤∣S∣≤2000 (Here, ∣S∣ denotes the length of S.)
- 1≤∣X∣≤8
- 1≤∣Y∣≤8
样例 1 解释:
例如,字符串 001111011 是一个“好字符串”,它可通过将 S 中的每个 ? 替换为 0 或 1 得到。若以 t=(x,y,x) 作为初始序列启动该过程,则得到 T=0?1?1?0?1。再将 T 中的每个 ? 替换为 0 或 1,即可得到 001111011,因此 001111011 是一个好字符串。
除此之外,还有四个字符串 001011010、001011011、001011110、001011111 满足条件。不存在其他满足条件的字符串,因此输出 5。
样例 2 解释:
注意:y 在 t 中不能连续出现。
样例 3 解释:
注意:你需要输出满足条件的字符串个数对 998244353 取模的结果。
约束条件
- S、X、Y 均为仅由
0、1和?组成的字符串。 - 1≤∣S∣≤2000(其中 ∣S∣ 表示 S 的长度)。
- 1≤∣X∣≤8
- 1≤∣Y∣≤8
输入解题思路,AI测评打分。不知道怎么写?