Hongcow Masters the Cyclic Shift

题意翻译

- 设 $X$ 是字符串的集合。定义 $S_X=\{x_1+\cdots+x_k|k\in \mathbb{N},x_1,...,x_k\in X\}$，即由 $X$ 中字符串以任意顺序、任意次数能拼接组成的字符串的集合。注意到当 $X$ 不空时 $S_X$ 一定是无穷集合。 - 进一步地，设 $s=x_1+\cdots+x_k$，其中 $x_1,...,x_k$ 都是 $X$ 中的字符串。显然 $s\in S_X$。称 $s$ 在 $X$ 下是好的，当且仅当恰好存在 $k$ 个整数 $i\in [0,|s|)$， 使得 $s$ 循环移位 $k$ 位后是 $S_X$ 中的串。这里，定义一个串循环移位 $k$ 位所形成的串是把这个串的最后 $k$ 个字符顺序不变地移动到该串开头所形成的串。注意到如果存在 $s=x_1+\cdots+x_{k_1}=x'_1+\cdots+x'_{k_2}$ 且 $k_1\neq k_2$，那么 $s$ 不可能是好的。 - 称字符串集合 $X$ 是好的当且仅当对于任意的 $s\in S_X$，$s$ 是好的。 - 给定 $n$ 个字符串串 $A_1,...,A_n$。计算有多少个区间 $[l,r]$ 满足 $1\leq l\leq r\leq n$，且字符串集合 $\{A_l,...,A_r\}$ 是好的。 - $n\leq 30$，$\sum{|A_i|}\leq 10^5$，保证 $A_i$ 均由小写英文字母构成。

题目描述

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).

输入输出格式

输入格式

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} $ ().

输出格式

Print a single integer, the number of nonempty contiguous sublists that are stable.

输入输出样例

输入样例 #1

4
a
ab
b
bba

输出样例 #1

7

输入样例 #2

5
hh
ee
ll
ll
oo

输出样例 #2

0

输入样例 #3

6
aab
ab
bba
b
ab
c

输出样例 #3

13

说明

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} $ .

题意翻译

- 设 $X$ 是字符串的集合。定义 $S_X=\{x_1+\cdots+x_k|k\in \mathbb{N},x_1,...,x_k\in X\}$，即由 $X$ 中字符串以任意顺序、任意次数能拼接组成的字符串的集合。注意到当 $X$ 不空时 $S_X$ 一定是无穷集合。 - 进一步地，设 $s=x_1+\cdots+x_k$，其中 $x_1,...,x_k$ 都是 $X$ 中的字符串。显然 $s\in S_X$。称 $s$ 在 $X$ 下是好的，当且仅当恰好存在 $k$ 个整数 $i\in [0,|s|)$， 使得 $s$ 循环移位 $k$ 位后是 $S_X$ 中的串。这里，定义一个串循环移位 $k$ 位所形成的串是把这个串的最后 $k$ 个字符顺序不变地移动到该串开头所形成的串。注意到如果存在 $s=x_1+\cdots+x_{k_1}=x'_1+\cdots+x'_{k_2}$ 且 $k_1\neq k_2$，那么 $s$ 不可能是好的。 - 称字符串集合 $X$ 是好的当且仅当对于任意的 $s\in S_X$，$s$ 是好的。 - 给定 $n$ 个字符串串 $A_1,...,A_n$。计算有多少个区间 $[l,r]$ 满足 $1\leq l\leq r\leq n$，且字符串集合 $\{A_l,...,A_r\}$ 是好的。 - $n\leq 30$，$\sum{|A_i|}\leq 10^5$，保证 $A_i$ 均由小写英文字母构成。