简单九连环

Luogu

IDLGP9229

Time1000ms

Memory512MB

DifficultyP5

动态规划 DP2023O2优化洛谷月赛

一个简单九连环，可以看作两个 `01` 串——规则串 $s$ 和状态串 $t$，满足 $|s|=|t|-1$。其中 $t_i = \texttt 1$ 表示第 $i$ 个环是装上的，$t_i = \texttt 0$ 表示第 $i$ 个环是拆下的。 $s$ 在同一局游戏中是不变的，而 $t$ 每步会变化一个位置上的值（从 `0` 变成 `1` 或从 `1` 变成 `0`）。简单九连环被拆下，当且仅当 $t_i$ 全是 `0`；简单九连环被装上，当且仅当 $t_i$ 全是 `1`。简单九连环规定，$t_i$ 可以变化，当且仅当 $t_{1\sim i-1}$ 是 $s$ 的一个**后缀**。可以看出，传统的九连环就是 $s$ 为 `00...01` 的特殊情形。给出一个 $s$，问从拆下状态到装上状态至少需要几步，答案对 $10^9+7$ 取模。 ## Input 第一行一个整数 $n$，表示 $s$ 的长度。**注意不是环的数量。** 第二行一个 `01` 串 $s$。 ## Output 一行一个整数，表示答案对 $10^9+7$ 取模后的值。 [samples] ## Background **提示：此题有大样例。** **提示：本题中的九连环与传统九连环不同。** 九连环是一种源于中国的传统智力游戏。如图所示，九个的圆环套在一把“剑”上，并且互相牵连。 ![](https://cdn.luogu.com.cn/upload/pic/17568.png) 在传统的九连环中，第 $k(k\ge 2)$ 个环可以装上“剑”（记为 $1$）或拆下“剑”（记为 $0$），当且仅当第 $k-1$ 个环在剑上，且再之前的环不在剑上；特别地，第 $1$ 个环可以任意上下。本题中我们将会讨论更一般的情形，虽然这种简单九连环不一定可以在物理意义上造出。 ## Note ### 样例 1 解释初始时刻所有环都不在简单九连环的剑上，状态串 $t$ 为 `0000`。第 1 步装上第 $1$ 个环，$t$ 变成 `1000`。第 2 步装上第 $2$ 个环，$t$ 变成 `1100`。第 3 步装上第 $3$ 个环，$t$ 变成 `1110`。接下来你不能直接装上第 $4$ 个环，因为 `111` 并不是规则串 $s$ `011` 的后缀。因此第 4 步应拆下第 $1$ 个环，$t$ 变成 `0110`。然后第 5 步装上第 $4$ 个环，$t$ 变成 `0111`。最后一步装上第 $1$ 个环，$t$ 变成 `1111`，完成目标。 ### 样例 2 解释这就是传统的九连环，且恰好有 $9$ 个环。 ### 样例 3 解释样例 3 满足测试点 $7$ 的限制。 ### 样例 4 解释样例 4 满足测试点 $15$ 的限制。 ### 数据规模与约定对于 $100\%$ 的数据，$1\le n\le 2000$，$s_i\in\{\texttt 0,\texttt 1\}$。 |测试点编号|$\vert s\vert\le$|特殊性质| |:-:|:-:|:-:| |$1\sim 3$|$3$|| |$4\sim 6$|$15$|| |$7\sim 11$|$300$|| |$12\sim 13$|$1000$|| |$14$|$2000$|$s_i$ 全为 `0`| |$15\sim 17$|$2000$|$s$ 末尾为 `1`，其余位置为 `0`| |$18\sim 25$|$2000$||

Samples

Input #1

3
011

Output #1

Input #2

8
00000001

Output #2

Input #3

见附件中的 samples/rings3.in

Output #3

见附件中的 samples/rings3.ans

Input #4

见附件中的 samples/rings4.in

Output #4

见附件中的 samples/rings4.ans

API Response (JSON)

{
  "problem": {
    "name": "简单九连环",
    "description": {
      "content": "一个简单九连环，可以看作两个 `01` 串——规则串 $s$ 和状态串 $t$，满足 $|s|=|t|-1$。其中 $t_i = \\texttt 1$ 表示第 $i$ 个环是装上的，$t_i = \\texttt 0$ 表示第 $i$ 个环是拆下的。 $s$ 在同一局游戏中是不变的，而 $t$ 每步会变化一个位置上的值（从 `0` 变成 `1` 或从 `1` 变成 `0`）。简单九连环被拆下，当且",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9229"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "一个简单九连环，可以看作两个 `01` 串——规则串 $s$ 和状态串 $t$，满足 $|s|=|t|-1$。其中 $t_i = \\texttt 1$ 表示第 $i$ 个环是装上的，$t_i = \\texttt 0$ 表示第 $i$ 个环是拆下的。\n\n$s$ 在同一局游戏中是不变的，而 $t$ 每步会变化一个位置上的值（从 `0` 变成 `1` 或从 `1` 变成 `0`）。简单九连环被拆下，当且...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments