{"raw_statement":[{"iden":"statement","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 list _A_.\n\nA list _X_ of strings is called _stable_ if the following condition holds.\n\nFirst, 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.\n\nCall a single message _good_ if the following conditions hold:\n\n*   Suppose the message is the concatenation of _k_ strings _w_1, _w_2, ..., _w__k_, where each _w__i_ is an element of _X_.\n*   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_.\n*   A message is good if and only if _m_ is exactly equal to _k_.\n\nThe list _X_ is called stable if and only if every element of _S__X_ is good.\n\nLet _f_(_L_) be 1 if _L_ is a stable list, and 0 otherwise.\n\nFind the sum of _f_(_L_) where _L_ is a nonempty **contiguous sublist** of _A_ (there are contiguous sublists in total)."},{"iden":"input","content":"The first line of input will contain a single integer _n_ (1 ≤ _n_ ≤ 30), denoting the number of strings in the list.\n\nThe next _n_ lines will each contain a string _s__i_ ()."},{"iden":"output","content":"Print a single integer, the number of nonempty **contiguous sublists** that are stable."},{"iden":"examples","content":"Input\n\n4\na\nab\nb\nbba\n\nOutput\n\n7\n\nInput\n\n5\nhh\nee\nll\nll\noo\n\nOutput\n\n0\n\nInput\n\n6\naab\nab\nbba\nb\nab\nc\n\nOutput\n\n13"},{"iden":"note","content":"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.\n\nFor 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_."}],"translated_statement":[{"iden":"statement","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] 中某些元素的拼接。你可以任意多次使用任意元素，并可以按任意顺序拼接这些元素。令 #cf_span[SX] 表示你可以从该列表构造出的所有消息的集合。显然，如果列表非空，则该集合具有无限大小。\n\n称单个消息为 _好的_，当且仅当满足以下条件：\n\n列表 #cf_span[X] 被称为稳定的，当且仅当 #cf_span[SX] 中的每个元素都是好的。\n\n令 #cf_span[f(L)] 为 #cf_span[1]（如果 #cf_span[L] 是稳定列表），否则为 #cf_span[0]。\n\n求所有非空 *连续子列表* #cf_span[L] 的 #cf_span[f(L)] 之和（总共有  个连续子列表）。\n\n输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 30]），表示列表中字符串的数量。\n\n接下来的 #cf_span[n] 行，每行包含一个字符串 #cf_span[si]（）。\n\n请输出一个整数，表示稳定的非空 *连续子列表* 的数量。\n\n对于第一个样例，共有 #cf_span[10] 个子列表需要考虑。子列表 [\"_a_\", \"_ab_\", \"_b_\"], [\"_ab_\", \"_b_\", \"_bba_\"], 和 [\"_a_\", \"_ab_\", \"_b_\", \"_bba_\"] 不是稳定的。其余七个子列表是稳定的。\n\n例如，#cf_span[X] = [\"_a_\", \"_ab_\", \"_b_\"] 不是稳定的，因为消息 \"_ab_\" + \"_ab_\" = \"_abab_\" 有四个循环移位 [\"_abab_\", \"_baba_\", \"_abab_\", \"_baba_\"]，它们都是 #cf_span[SX] 中的元素。"},{"iden":"input","content":"输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 30]），表示列表中字符串的数量。接下来的 #cf_span[n] 行，每行包含一个字符串 #cf_span[si]（）。"},{"iden":"output","content":"请输出一个整数，表示稳定的非空 *连续子列表* 的数量。"},{"iden":"examples","content":"输入\n4\na\nab\nb\nbba\n输出\n7\n\n输入\n5\nh\nh\ne\ne\nl\nl\nl\nl\no\no\n输出\n0\n\n输入\n6\na\na\nb\nab\nb\nb\na\nb\na\nb\nc\n输出\n13"},{"iden":"note","content":"对于第一个样例，共有 #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] 中的元素。"}],"sample_group":[],"show_order":[],"formal_statement":"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 strings from $ L $, with repetition and arbitrary order allowed (i.e., the free monoid generated by $ L $).\n\nA 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 $.\n\nDefine the indicator function:\n$$\nf(L) = \n\\begin{cases}\n1 & \\text{if } L \\text{ is stable}, \\\\\n0 & \\text{otherwise}.\n\\end{cases}\n$$\n\nLet $ \\mathcal{L} $ be the set of all nonempty contiguous sublists of $ A $. There are $ \\frac{n(n+1)}{2} $ such sublists.\n\n**Objective:** Compute\n$$\n\\sum_{L \\in \\mathcal{L}} f(L)\n$$\n\nThat is, count the number of nonempty contiguous sublists $ L $ of $ A $ such that the monoid $ S_L $ is closed under cyclic shifts.","simple_statement":null,"has_page_source":false}