English · Original
Chinese · Translation
Formal · Original
Hongcow's teacher heard that Hongcow had learned about the cyclic shift, and decided to set the following problem for him.
You are given a list of _n_ strings _s_1, _s_2, ..., _s__n_ contained in the list _A_.
A list _X_ of strings is called _stable_ if the following condition holds.
First, a _message_ is defined as a concatenation of some elements of the list _X_. You can use an arbitrary element as many times as you want, and you may concatenate these elements in any arbitrary order. Let _S__X_ denote the set of of all messages you can construct from the list. Of course, this set has infinite size if your list is nonempty.
Call a single message _good_ if the following conditions hold:
* Suppose the message is the concatenation of _k_ strings _w_1, _w_2, ..., _w__k_, where each _w__i_ is an element of _X_.
* Consider the |_w_1| + |_w_2| + ... + |_w__k_| cyclic shifts of the string. Let _m_ be the number of these cyclic shifts of the string that are elements of _S__X_.
* A message is good if and only if _m_ is exactly equal to _k_.
The list _X_ is called stable if and only if every element of _S__X_ is good.
Let _f_(_L_) be 1 if _L_ is a stable list, and 0 otherwise.
Find the sum of _f_(_L_) where _L_ is a nonempty **contiguous sublist** of _A_ (there are contiguous sublists in total).
## Input
The first line of input will contain a single integer _n_ (1 ≤ _n_ ≤ 30), denoting the number of strings in the list.
The next _n_ lines will each contain a string _s__i_ ().
## Output
Print a single integer, the number of nonempty **contiguous sublists** that are stable.
[samples]
## Note
For the first sample, there are 10 sublists to consider. Sublists \["_a_", "_ab_", "_b_"\], \["_ab_", "_b_", "_bba_"\], and \["_a_", "_ab_", "_b_", "_bba_"\] are not stable. The other seven sublists are stable.
For example, _X_ = \["_a_", "_ab_", "_b_"\] is not stable, since the message "_ab_" + "_ab_" = "_abab_" has four cyclic shifts \["_abab_", "_baba_", "_abab_", "_baba_"\], which are all elements of _S__X_.
Hongcow 的老师听说 Hongcow 学习了循环移位，于是给他布置了以下问题。
给你一个包含 #cf_span[n] 个字符串 #cf_span[s1, s2, ..., sn] 的列表 #cf_span[A]。
一个字符串列表 #cf_span[X] 被称为 _稳定的_，当且仅当满足以下条件。
首先，定义一个 _消息_ 为列表 #cf_span[X] 中某些元素的拼接。你可以任意多次使用任意元素，并可以按任意顺序拼接这些元素。令 #cf_span[SX] 表示你可以从该列表构造出的所有消息的集合。显然，如果列表非空，则该集合具有无限大小。
称单个消息为 _好的_，当且仅当满足以下条件：
列表 #cf_span[X] 被称为稳定的，当且仅当 #cf_span[SX] 中的每个元素都是好的。
令 #cf_span[f(L)] 为 #cf_span[1]（如果 #cf_span[L] 是稳定列表），否则为 #cf_span[0]。
求所有非空 *连续子列表* #cf_span[L] 的 #cf_span[f(L)] 之和（总共有 个连续子列表）。
输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 30]），表示列表中字符串的数量。
接下来的 #cf_span[n] 行，每行包含一个字符串 #cf_span[si]（）。
请输出一个整数，表示稳定的非空 *连续子列表* 的数量。
对于第一个样例，共有 #cf_span[10] 个子列表需要考虑。子列表 ["_a_", "_ab_", "_b_"], ["_ab_", "_b_", "_bba_"], 和 ["_a_", "_ab_", "_b_", "_bba_"] 不是稳定的。其余七个子列表是稳定的。
例如，#cf_span[X] = ["_a_", "_ab_", "_b_"] 不是稳定的，因为消息 "_ab_" + "_ab_" = "_abab_" 有四个循环移位 ["_abab_", "_baba_", "_abab_", "_baba_"]，它们都是 #cf_span[SX] 中的元素。
## Input
输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 30]），表示列表中字符串的数量。接下来的 #cf_span[n] 行，每行包含一个字符串 #cf_span[si]（）。
## Output
请输出一个整数，表示稳定的非空 *连续子列表* 的数量。
[samples]
## Note
对于第一个样例，共有 #cf_span[10] 个子列表需要考虑。子列表 ["_a_", "_ab_", "_b_"], ["_ab_", "_b_", "_bba_"], 和 ["_a_", "_ab_", "_b_", "_bba_"] 不是稳定的。其余七个子列表是稳定的。例如，#cf_span[X] = ["_a_", "_ab_", "_b_"] 不是稳定的，因为消息 "_ab_" + "_ab_" = "_abab_" 有四个循环移位 ["_abab_", "_baba_", "_abab_", "_baba_"]，它们都是 #cf_span[SX] 中的元素。
Let $ A = [s_1, s_2, \dots, s_n] $ be a list of $ n $ strings over a finite alphabet.
For a nonempty contiguous sublist $ L \subseteq A $, define $ S_L $ as the set of all finite concatenations of strings from $ L $, with repetition and arbitrary order allowed (i.e., the free monoid generated by $ L $).
A sublist $ L $ is called **stable** if and only if for every message $ w \in S_L $, **all cyclic shifts of $ w $** are also in $ S_L $.
Define the indicator function:
$$
f(L) =
\begin{cases}
1 & \text{if } L \text{ is stable}, \\
0 & \text{otherwise}.
\end{cases}
$$
Let $ \mathcal{L} $ be the set of all nonempty contiguous sublists of $ A $. There are $ \frac{n(n+1)}{2} $ such sublists.
**Objective:** Compute
$$
\sum_{L \in \mathcal{L}} f(L)
$$
That is, count the number of nonempty contiguous sublists $ L $ of $ A $ such that the monoid $ S_L $ is closed under cyclic shifts.
API Response (JSON)
{
"problem": {
"name": "E. Hongcow Masters the Cyclic Shift",
"description": {
"content": "Hongcow's teacher heard that Hongcow had learned about the cyclic shift, and decided to set the following problem for him. You are given a list of _n_ strings _s_1, _s_2, ..., _s__n_ contained in the",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 5000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF744E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Hongcow's teacher heard that Hongcow had learned about the cyclic shift, and decided to set the following problem for him.\n\nYou are given a list of _n_ strings _s_1, _s_2, ..., _s__n_ contained in the...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Hongcow 的老师听说 Hongcow 学习了循环移位，于是给他布置了以下问题。\n\n给你一个包含 #cf_span[n] 个字符串 #cf_span[s1, s2, ..., sn] 的列表 #cf_span[A]。\n\n一个字符串列表 #cf_span[X] 被称为 _稳定的_，当且仅当满足以下条件。\n\n首先，定义一个 _消息_ 为列表 #cf_span[X] 中某些元素的拼接。你可以任意多次...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ A = [s_1, s_2, \\dots, s_n] $ be a list of $ n $ strings over a finite alphabet.\n\nFor a nonempty contiguous sublist $ L \\subseteq A $, define $ S_L $ as the set of all finite concatenations of st...",
"is_translate": false,
"language": "Formal"
}
]
}