#P16386. [2024年南京集训]消逝的传承
[2024年南京集训]消逝的传承
题目描述
给定一个长度为 、仅包含字符 0、1 和 ? 的字符串 。
需要计算满足下列条件的字符串序列
的数量:
- 的长度恰好为 ,并且只包含字符
0和1; - 对于每个 ,字符串 可以由 插入一个字符
0或1得到; - 对于最终字符串 的每一位 :
- 若 为
0或1,则必须满足 ; - 若 为
?,则 可以为0或1。
- 若 为
求方案数对
取模后的结果。
其中, 是空字符串。
输入格式
第一行包含一个整数 。
第二行包含一个长度为 、仅由 0、1 和 ? 构成的字符串 。
输出格式
输出一行一个整数,表示满足条件的方案数量对 取模后的结果。
样例 1
输入
3
0?1
输出
6
样例解释
满足条件的 种方案分别为:
- ;
- ;
- ;
- ;
- ;
- 。
样例 2
输入
5
0111?
输出
24
数据范围与子任务
对于全部测试数据:
| 子任务 | 不超过 | 特殊性质 | 分值 |
|---|---|---|---|
| 1 | 无 | 10 | |
| 2 | |||
| 3 | A | 5 | |
| 4 | B | 25 | |
| 5 | 无 | 10 | |
| 6 | |||
| 7 | 15 | ||
| 8 |
特殊性质 A
字符串 仅包含字符 ?。
特殊性质 B
字符串 中字符 0 和 1 的出现次数之和不超过 。