小红的01子序列计数（hard）_

$\hspace{15pt}$ 小红定义一个字符串的权值为，该字符串包含的 $\texttt{$ 子序列 $^{\texttt{[1]}}$ 的数量。

$\hspace{15pt}$ 现在小红拿到了一个由字符 $\texttt{`0'}$ 和 $\texttt{`1'}$ 组成的字符串环（即最后一个字符下一个是第一个字符）。现在小红想知道，这个环的所有长度不小于 $2$ 的连续子串 $^{\texttt{[2]}}$ 权值之和是多少？
$\hspace{15pt}$ 由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

$\hspace{15pt}$ $\texttt{$ 子序列 $^{\texttt{[1]}}$ 为从原字符串中删除任意个（可以为零、可以为全部）字符得到的新字符串，字符串恰好为 $\texttt{$ 。
$\hspace{15pt}$ 子串 $^{\texttt{[2]}}$ 为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。在本题中，环上的子串为，任取两个下标 $l$ 和 $r$ ，从 $l$ 不断向右取直到 $r$ 形成的连续子串；特殊的，若 $r < l$ ，则会从 $l$ 向右取到最后一个字符，之后从第一个字符取到 $r$ 。

$\hspace{15pt}$ 在这个样例中，长度为 $2$ 的连续子串有 $3$ 个：
$\hspace{23pt}\bullet\,$ $\texttt{$ ，权值为 $0$ ；
$\hspace{23pt}\bullet\,$ $\texttt{$ ，权值为 $1$ ；
$\hspace{23pt}\bullet\,$ $\texttt{$ ，权值为 $0$ 。
$\hspace{15pt}$ 长度为 $3$ 的连续子串有 $3$ 个：
$\hspace{23pt}\bullet\,$ $\texttt{$ ，权值为 $2$ ；
$\hspace{23pt}\bullet\,$ $\texttt{$ ，权值为 $1$ ；
$\hspace{23pt}\bullet\,$ $\texttt{$ ，权值为 $0$ 。

$\hspace{15pt}$ 所有长度不小于 $2$ 的连续子串的权值之和为 $0 + 1 + 0 + 2 + 1 + 0 = 4$ 。

#超时了，思路应该没问题；主要是遍历以每个字符为开头的，长度大于2小于等于n的权重，再求和 n = int(input()) s = str(input()) s_ring = s+s s_ring_01sum = 0 for i in range(n):#头尾字符串的每一个字符为开头取取子串 temp_01sum = 0#索引为I开头的子串取权重之和 value = 0#i开头长度为j+1的子串权重; if s_ring[i] == '0': cnt_0 = 1 cnt_1 = 0 else: cnt_0 = 0 cnt_1 = 1 for j in range(1,n):#计算子串大于二的权重; if s_ring[i+j] == '0': cnt_0 +=1 else: cnt_1 += 0 value += cnt_0 print(value) temp_01sum +=value s_ring_01sum += temp_01sum M = 10**9+7 print(s_ring_01sum%M)

小红的01子序列计数（hard）

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题