题目描述
对于一个由 0 和 1 组成的序列，我们定义它的“对称三元组”数量为满足 1≤l<m<r≤n 且 al=ar 的有序三元组 (l,m,r) 的个数。例如，“0110”的对称三元组数量为 2，因为包含两个对称三元组“010”。
给定一个长度为 n 的非负整数数组 b1,b2,…,bn，需要构造一个 01 串 S，使得对任意 1≤i≤n，S 的前缀长度为 i 时的对称三元组数量恰好等于 bi。若无解，输出 -1；否则输出任意一个可行解。
解题思路与方法
1. 前缀对称三元组增量公式
记当前已构造前缀长度为 i−1 的串为 S[1..i−1]，其对称三元组数量为 fi−1=bi−1。若在位置 i 处添加字符 b∈{0,1}，则新增的所有对称三元组都形如 bxb，其中中间字符 x 来自前缀中所有与 b 相等的位置。
- 设此前前缀中字符 b 出现次数为
c，下标和为 s（下标从 1 开始）；
