B. So You Think You Can Count?

Codeforces

IDCF10134B

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Elissa is so clever girl, even though her age is 5 years only. Yesterday she spent all the day learning how to count. Currently she is able to solve many complex counting questions, so she decided to invent a new counting problem in order to help preparing this contest. Elissa will give you a string s consisting of digits only (from '_0_' to '_9_'), and your task is to count in how many ways you can divide the given string to sub-strings such that each sub-string is a beautiful sub-string. A beautiful sub-string b is a sub-string from string s, such that b contains unique digits only (i.e. each digit from '_0_' to '_9_' can exist at most one time). Elissa thinks that no one can solve this problem because it is very hard. Can you? The first line contains an integer n (1 ≤ n ≤ 104), where n is the length of the string s. The second line contains a string s consisting of digits only. Print the number of ways you can divide the given string to sub-strings such that each sub-string is a beautiful sub-string. Since the number of ways may be too large, print the answer modulo 109 + 7. A sub-string of the string s is a sequence sl, sl + 1, ..., sr for some integers (l, r) such that (1 ≤ l ≤ r ≤ n), where n is the length of the string s. In the first test case you can divide the given string in 6 ways, which are: ## Input The first line contains an integer n (1 ≤ n ≤ 104), where n is the length of the string s. The second line contains a string s consisting of digits only. ## Output Print the number of ways you can divide the given string to sub-strings such that each sub-string is a beautiful sub-string. Since the number of ways may be too large, print the answer modulo 109 + 7. [samples] ## Note A sub-string of the string s is a sequence sl, sl + 1, ..., sr for some integers (l, r) such that (1 ≤ l ≤ r ≤ n), where n is the length of the string s.In the first test case you can divide the given string in 6 ways, which are: 1|2|1|3 1|2|13 1|21|3 1|213 12|1|3 12|13 Note that you cannot divide it to (121|3) because the first sub-string contain the digit '_1_' twice.

**Definitions** Let $ n \in \mathbb{Z} $ be the length of the string $ s \in \{0,1,\dots,9\}^n $. A *beautiful substring* is a contiguous substring containing only distinct digits. **Constraints** 1. $ 1 \leq n \leq 10^4 $ 2. Each character of $ s $ is a digit from '0' to '9'. **Objective** Count the number of ways to partition $ s $ into a sequence of contiguous beautiful substrings. Let $ dp[i] $ denote the number of valid partitions of the prefix $ s[0:i] $ (0-indexed, length $ i $). Then: $$ dp[0] = 1 $$ $$ dp[i] = \sum_{\substack{0 \leq j < i \\ s[j:i] \text{ is beautiful}}} dp[j] \quad \text{for } 1 \leq i \leq n $$ Output $ dp[n] \mod (10^9 + 7) $.

API Response (JSON)

{
  "problem": {
    "name": "B. So You Think You Can Count?",
    "description": {
      "content": "Elissa is so clever girl, even though her age is 5 years only. Yesterday she spent all the day learning how to count. Currently she is able to solve many complex counting questions, so she decided to ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10134B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Elissa is so clever girl, even though her age is 5 years only. Yesterday she spent all the day learning how to count. Currently she is able to solve many complex counting questions, so she decided to ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the string $ s \\in \\{0,1,\\dots,9\\}^n $.  \nA *beautiful substring* is a contiguous substring containing only distinct digits.  \n\n**Constraint...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments