链接：https://ac.nowcoder.com/acm/contest/58604/G 来源：牛客网 小红拿到了一个仅由数字字符组成的字符串。她准备选择一个非空子序列，使得该子序列中不包含连续的"61"子串。 小红想知道，有多少种不同的子序列选择方式？答案对 1 0 9 + 7 10 9 +7取模。

我们可以使用动态规划来解决该问题。

设 $f_i$ 表示以第 $i$ 个字符结尾的、不包含连续的 "61" 子串的子序列个数。那么我们可以考虑第 $i$ 个字符的状态转移：

1. 如果第 $i$ 个字符不是 "6" 或 "1"，那么它可以单独作为一个子序列，也可以加入到以第 $i-1$ 个字符结尾的子序列中。因此，状态转移方程为：

$$
f_i = (f_{i-1} + 1) \bmod 10^9 + 7
$$

2. 如果第 $i$ 个字符是 "6" 或 "1"，那么它只能单独作为一个子序列，不能加入到以第 $i-1$ 个字符结尾的子序列中，因为这样会产生连续的 "61" 子串。因此，状态转移方程为：

$$
f_i = 1
$$

最终的答案即为 $f_1+f_2+\cdots+f_n$。

时间复杂度为 $O(n)$。

相关问题

链接：https://ac.nowcoder.com/acm/contest/59840/K 来源：牛客网 给定 � n 个坐标，求其中 3 3 个坐标能表示一个等腰三角形的组数。 三点共线不算三角形，等边三角形为特殊的等腰三角形。

这道题可以用哈希表来解决。首先枚举三角形的顶点，然后计算出这个顶点到其它点的距离，并将距离存入哈希表中。接着枚举其它点作为三角形的另一个顶点，计算出这个点到剩下的点的距离，并在哈希表中查找是否存在与之前顶点距离相等的点，如果存在，则说明这三个点可以组成等腰三角形。

具体实现可以使用 STL 中的 unordered_map 来实现哈希表。时间复杂度为 O(n^2)。

以下是代码实现：

链接：https://ac.nowcoder.com/acm/contest/60282/C 来源：牛客网 小红拿到了一个数组，她可以进行若干次以下操作： 1.选择一个元素，花费 p，使其加 x。 1.选择一个元素，花费 q，使其减 y。 小红希望若干次操作后，数组的平均数是一个整数。你能帮小红求出最小的总代价吗？

对于给定的数组，要使得操作后的数组平均数是一个整数，可以通过以下方法计算最小的总代价：

1. 首先，计算数组的总和sum和元素个数n。
2. 判断sum是否能够整除n，如果不能整除，则无法使得平均数为整数，返回-1。
3. 计算目标平均数target = sum / n。
4. 统计数组中大于target的元素个数count1和小于target的元素个数count2。
5. 计算增加操作的总代价为count1 * p。
6. 计算减少操作的总代价为count2 * q。
7. 返回增加操作总代价和减少操作总代价的和作为最小的总代价。

注意：在计算代价时，需要考虑p、q、x、y的取值范围，以及可能存在的整数溢出情况。

希望能帮到你！如果还有其他问题，请继续提问。