#P15469. 信标编码

    ID: 14684 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-线性 DP计数 DP预处理下一出现位置添加/删除事件增量维护势能分析

信标编码

题目描述

某通信系统会把一段二进制信号拆分成若干个 标准信标段。

一个字符串被称为标准信标段,当且仅当它的长度为偶数,并且前一半字符全为 0,后一半字符全为 1。

例如:

  • 01 是标准信标段;
  • 0011 是标准信标段;
  • 000111 是标准信标段。

如果一个字符串可以由若干个标准信标段依次连接而成,那么称这个字符串是 合法编码。

例如,0011、01001101 是合法编码,而 10、010001101 不是合法编码。

现在给定一个由 0、1、? 三种字符组成的字符串 ss。你需要把每个 ? 独立替换成 0 或 1。

请计算有多少种替换方案,使得替换后的字符串是合法编码。

答案对 109+710^9+7 取模。

输入格式

输入一行一个字符串 ss。

输出格式

输出一行一个整数,表示合法替换方案数。

样例 1 输入

0?0????1

样例 1 输出

6

样例 1 解释

以下方案是合法的:

00001111
00011101
01000111
01001101
01010011
01010101

样例 2,3,4,5

见选手目录下:

  • string/ex_string.2-5.in
  • string/ex_string.2-5.out

其中:

  • 样例 2 满足 ∣s∣≤3000|s|\le 3000;
  • 样例 3 满足 ∣s∣≤5×105|s|\le 5\times 10^5,且所有字符都是 ?;
  • 样例 4 满足 ∣s∣≤5×105|s|\le 5\times 10^5,且 si≠s_i\ne w;
  • 样例 5 满足 ∣s∣≤5×105|s|\le 5\times 10^5。

备注:原题中出现了“si≠s_i\ne w”,但字符集只有 0、1、?,此处疑似原题笔误。为避免改变原题信息,本改写版保留该特殊性质的原文字面内容。

测试点约束

对于所有数据,满足:

2≤∣s∣≤5×1062\le |s|\le 5\times 10^6

并且 ∣s∣|s| 为偶数。

各子任务如下:

  • 子任务 1:∣s∣≤20|s|\le 20,无特殊性质,分值 15。
  • 子任务 2:∣s∣≤200|s|\le 200,无特殊性质,分值 10。
  • 子任务 3:∣s∣≤3000|s|\le 3000,无特殊性质,分值 15。
  • 子任务 4:∣s∣≤5×105|s|\le 5\times 10^5,且所有字符都是 ?,分值 5。
  • 子任务 5:∣s∣≤5×105|s|\le 5\times 10^5,且 si≠s_i\ne w,分值 15。
  • 子任务 6:∣s∣≤2×105|s|\le 2\times 10^5,无特殊性质,分值 10。
  • 子任务 7:∣s∣≤5×105|s|\le 5\times 10^5,无特殊性质,分值 10。
  • 子任务 8:∣s∣≤106|s|\le 10^6,无特殊性质,分值 10。
  • 子任务 9:∣s∣≤5×106|s|\le 5\times 10^6,无特殊性质,分值 10。