#ABC484G. 通配符构造
通配符构造
通配符构造
题目描述
给定由 0、1、? 组成的字符串 。
称按以下过程得到的字符串为「好串」:
- 选择由 与 组成的序列 ,使得不存在整数 ()满足 。
- 令 ,其中若 为 则 ,若 为 则 。
- 令 为 依次拼接得到的字符串。
- 把 中的每个
?替换为0或1。
求把 中的每个 ? 替换为 0 或 1 后能得到的好串个数,对 取模。
输入格式
输入共三行,依次为字符串 、、。
输出格式
输出一行一个整数,表示好串个数对 取模的结果。
?0??11?1?
0?1
?1?
5
样例 1 解释
例如取 ,则 0?1?1?0?1,把其中的 ? 适当替换后可以得到 001111011,因此 001111011 是好串。
除此之外,001011010、001011011、001011110、001011111 这四个串也满足条件,因此答案为 。
0?10?1?01?
???
?????
0
样例 2 解释
注意 中不能出现连续的 。
????????????1???1??0??????1???????1????????1????????????????0
?0??
?
992356689
样例 3 解释
答案需要对 取模。
数据范围
对于所有测试数据,保证:
- 均由
0、1、?组成; - ;
- ,;
- 所有输入值均为整数。
子任务
本题共 20 个测试点,按测试点计分:
| 测试点 | 分值 | 每个测试点 | 特殊性质 |
|---|---|---|---|
| 无特殊限制 |
每个测试点单独评分,全部测试点的得分之和即为本题得分。
相关
在下列比赛中: