F. Rikka with Nice Counting Striking Back

Codeforces

IDCF10201F

Time8000ms

Memory1024MB

Difficulty—

English · Original

Formal · Original

As we know, Yuta is poor at counting numbers. Rikka is worrying about this situation, so she gives Yuta some counting tasks to practice. Here is one of them: In computer programming, a string is traditionally a sequence of characters and a substring of a string is a contiguous sequence of characters within the string. For instance, _snowball_ is a string, _now_ is a substring of _snowball_ and _bow_ is not a substring of _snowball_. Moreover, the concatenation of two strings $U$ and $V$ is named as $U V$, that is, if $U$ is _snow_ and $V$ is _ball_, then $U V$ is _snowball_. Rikka has a string $S$ of length $n$ and she wants Yuta to count how many distinct _nice_ strings in total. Here, she calls a non-empty string $T$ _nice_ if It is too difficult for Yuta. Can you help him? The input contains several test cases, and the first line contains a single integer $T$ ($1 <= T <= 1000$), the number of test cases. For each test case, the only line contains a single string $S$ of length $n$ ($1 <= n <= 2 times 10^5$) with only lowercase letters. The input guarantees that the sum of $n$ in all test cases is at most $5 times 10^6$. For each test case, output a single line with a single integer, the answer. ## Input The input contains several test cases, and the first line contains a single integer $T$ ($1 <= T <= 1000$), the number of test cases.For each test case, the only line contains a single string $S$ of length $n$ ($1 <= n <= 2 times 10^5$) with only lowercase letters.The input guarantees that the sum of $n$ in all test cases is at most $5 times 10^6$. ## Output For each test case, output a single line with a single integer, the answer. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case, let $ S $ be a string of length $ n $ over the alphabet $ \Sigma = \{a, b, \dots, z\} $. Let $ \mathcal{U}(S) $ denote the set of all non-empty substrings of $ S $. **Constraints** 1. $ 1 \le T \le 1000 $ 2. For each test case: $ 1 \le n \le 2 \times 10^5 $ 3. $ \sum_{\text{all test cases}} n \le 5 \times 10^6 $ **Objective** Compute $ \left| \mathcal{U}(S) \right| $, the number of distinct non-empty substrings of $ S $.

API Response (JSON)

{
  "problem": {
    "name": "F. Rikka with Nice Counting Striking Back",
    "description": {
      "content": "As we know, Yuta is poor at counting numbers. Rikka is worrying about this situation, so she gives Yuta some counting tasks to practice. Here is one of them: In computer programming, a string is trad",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 8000,
      "memory_limit": 1048576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10201F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "As we know, Yuta is poor at counting numbers. Rikka is worrying about this situation, so she gives Yuta some counting tasks to practice. Here is one of them:\n\nIn computer programming, a string is trad...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ S $ be a string of length $ n $ over the alphabet $ \\Sigma = \\{a, b, \\dots, z\\} $.  \nLet $ \\mathcal{...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments