{"problem":{"name":"I. Fake News (hard)","description":{"content":"Now that you have proposed a fake post for the HC2 Facebook page, Heidi wants to measure the quality of the post before actually posting it. She recently came across a (possibly fake) article about th","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF802I"},"statements":[{"statement_type":"Markdown","content":"Now that you have proposed a fake post for the HC2 Facebook page, Heidi wants to measure the quality of the post before actually posting it. She recently came across a (possibly fake) article about the impact of fractal structure on multimedia messages and she is now trying to measure the self-similarity of the message, which is defined as\n\nwhere the sum is over all nonempty strings _p_ and is the number of occurences of _p_ in _s_ as a **substring**. (Note that the sum is infinite, but it only has a finite number of nonzero summands.)\n\nHeidi refuses to do anything else until she knows how to calculate this self-similarity. Could you please help her? (If you would like to instead convince Heidi that a finite string cannot be a fractal anyway – do not bother, we have already tried.)\n\n## Input\n\nThe input starts with a line indicating the number of test cases _T_ (1 ≤ _T_ ≤ 10). After that, _T_ test cases follow, each of which consists of one line containing a string _s_ (1 ≤ |_s_| ≤ 100 000) composed of lowercase letters (_a_\\-_z_).\n\n## Output\n\nOutput _T_ lines, every line containing one number – the answer to the corresponding test case.\n\n[samples]\n\n## Note\n\nA string _s_ contains another string _p_ as a substring if _p_ is a contiguous subsequence of _s_. For example, _ab_ is a substring of _cab_ but not of _acb_.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"既然你已经为 HC#cf_span[2] Facebook 页面提出了一条虚假帖子，Heidi 希望在实际发布之前评估该帖子的质量。她最近读到一篇（可能是虚假的）文章，讨论了分形结构对多媒体信息的影响，现在她试图测量该信息的自相似性，其定义为\n\n其中求和遍历所有非空字符串 #cf_span[p]，而  是 #cf_span[p] 在 #cf_span[s] 中作为 *子串* 出现的次数。（注意，该求和是无限的，但仅有有限个非零项。）\n\nHeidi 在弄清楚如何计算这个自相似性之前，拒绝做任何其他事情。你能帮帮她吗？（如果你想要说服 Heidi 无论如何有限字符串都不可能是分形——别费劲了，我们已经试过了。）\n\n输入的第一行包含测试用例的数量 #cf_span[T]（#cf_span[1 ≤ T ≤ 10]）。接下来是 #cf_span[T] 个测试用例，每个测试用例包含一行，由小写字母（_a_-_z_）组成的字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 100 000]）。\n\n请输出 #cf_span[T] 行，每行包含一个数字——对应测试用例的答案。\n\n字符串 #cf_span[s] 包含另一个字符串 #cf_span[p] 作为子串，当且仅当 #cf_span[p] 是 #cf_span[s] 的一个连续子序列。例如，_ab_ 是 _cab_ 的子串，但不是 _acb_ 的子串。\n\n## Input\n\n输入的第一行包含测试用例的数量 #cf_span[T]（#cf_span[1 ≤ T ≤ 10]）。接下来是 #cf_span[T] 个测试用例，每个测试用例包含一行，由小写字母（_a_-_z_）组成的字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 100 000]）。\n\n## Output\n\n请输出 #cf_span[T] 行，每行包含一个数字——对应测试用例的答案。\n\n[samples]\n\n## Note\n\n字符串 #cf_span[s] 包含另一个字符串 #cf_span[p] 作为子串，当且仅当 #cf_span[p] 是 #cf_span[s] 的一个连续子序列。例如，_ab_ 是 _cab_ 的子串，但不是 _acb_ 的子串。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ s $ be a string of length $ n $. The self-similarity of $ s $ is defined as:\n\n$$\n\\sum_{\\substack{p \\in \\Sigma^+ \\\\ p \\text{ is a substring of } s}} (\\text{occ}(p, s))^2\n$$\n\nwhere:\n- $ \\Sigma^+ $ denotes the set of all nonempty strings over the alphabet $ \\{a, b, \\dots, z\\} $,\n- $ \\text{occ}(p, s) $ is the number of occurrences of substring $ p $ in $ s $ (counting overlapping occurrences).\n\nEquivalently, since only substrings of $ s $ contribute nonzero terms, we may write:\n\n$$\n\\sum_{\\substack{p \\subseteq s \\\\ |p| \\geq 1}} (\\text{occ}(p, s))^2\n$$\n\nwhere the sum is over all nonempty contiguous substrings $ p $ of $ s $, and $ \\text{occ}(p, s) $ counts how many times $ p $ appears as a contiguous substring in $ s $.\n\n**Input:**  \n- $ T $ test cases.  \n- For each test case, a string $ s $ of length $ 1 \\leq |s| \\leq 100{,}000 $, consisting of lowercase English letters.\n\n**Output:**  \n- For each test case, output the value of the above sum.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF802I","tags":["string suffix structures"],"sample_group":[["4\naa\nabcd\nccc\nabcc","5\n10\n14\n12"]],"created_at":"2026-03-03 11:00:39"}}