D. Bacterial Melee

Codeforces

IDCF759D

Time2000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

Julia is conducting an experiment in her lab. She placed several luminescent bacterial colonies in a horizontal testtube. Different types of bacteria can be distinguished by the color of light they emit. Julia marks types of bacteria with small Latin letters "_a_", ..., "_z_". The testtube is divided into _n_ consecutive regions. Each region is occupied by a single colony of a certain bacteria type at any given moment. Hence, the population of the testtube at any moment can be described by a string of _n_ Latin characters. Sometimes a colony can decide to conquer another colony in one of the adjacent regions. When that happens, the attacked colony is immediately eliminated and replaced by a colony of the same type as the attacking colony, while the attacking colony keeps its type. Note that a colony can only attack its neighbours within the boundaries of the testtube. At any moment, at most one attack can take place. For example, consider a testtube with population "_babb_". There are six options for an attack that may happen next: * the first colony attacks the second colony (1 → 2), the resulting population is "_bbbb_"; * 2 → 1, the result is "_aabb_"; * 2 → 3, the result is "_baab_"; * 3 → 2, the result is "_bbbb_" (note that the result is the same as the first option); * 3 → 4 or 4 → 3, the population does not change. The pattern of attacks is rather unpredictable. Julia is now wondering how many different configurations of bacteria in the testtube she can obtain after a sequence of attacks takes place (it is possible that no attacks will happen at all). Since this number can be large, find it modulo 109 + 7. ## Input The first line contains an integer _n_ — the number of regions in the testtube (1 ≤ _n_ ≤ 5 000). The second line contains _n_ small Latin letters that describe the initial population of the testtube. ## Output Print one number — the answer to the problem modulo 109 + 7. [samples] ## Note In the first sample the population can never change since all bacteria are of the same type. In the second sample three configurations are possible: "_ab_" (no attacks), "_aa_" (the first colony conquers the second colony), and "_bb_" (the second colony conquers the first colony). To get the answer for the third sample, note that more than one attack can happen.

Julia 正在她的实验室中进行一项实验。她将若干发光的细菌菌落放置在一个水平的试管中。不同类型的细菌可以通过它们发出的光的颜色来区分。Julia 用小写拉丁字母 "_a_" 到 "_z_" 标记细菌的类型。试管被划分为 #cf_span[n] 个连续的区域。在任意时刻，每个区域都由一个特定类型细菌的菌落占据。因此，试管在任意时刻的种群可以用一个由 #cf_span[n] 个拉丁字符组成的字符串描述。有时，一个菌落会决定征服其相邻区域中的另一个菌落。当发生这种情况时，被攻击的菌落会立即被消灭，并被与攻击者相同类型的菌落取代，而攻击者的类型保持不变。注意，菌落只能攻击其在试管边界内的邻居。在任意时刻，最多只能发生一次攻击。例如，考虑一个种群为 "_babb_" 的试管。接下来可能发生六种攻击：攻击的模式相当不可预测。Julia 现在想知道，在经历一系列攻击后（可能根本不发生任何攻击），她可以获得多少种不同的细菌配置。由于这个数字可能很大，请对 #cf_span[109 + 7] 取模后输出。第一行包含一个整数 #cf_span[n] —— 试管中的区域数量（#cf_span[1 ≤ n ≤ 5 000]）。第二行包含 #cf_span[n] 个小写拉丁字母，描述试管的初始种群。请输出一个数 —— 该问题的答案，对 #cf_span[109 + 7] 取模。在第一个样例中，由于所有细菌类型相同，种群永远不会改变。在第二个样例中，有三种可能的配置："_ab_"（无攻击）、"_aa_"（第一个菌落征服第二个菌落）和 "_bb_"（第二个菌落征服第一个菌落）。对于第三个样例的答案，请注意可以发生多次攻击。 ## Input 第一行包含一个整数 #cf_span[n] —— 试管中的区域数量（#cf_span[1 ≤ n ≤ 5 000]）。第二行包含 #cf_span[n] 个小写拉丁字母，描述试管的初始种群。 ## Output 请输出一个数 —— 该问题的答案，对 #cf_span[109 + 7] 取模。 [samples] ## Note 在第一个样例中，由于所有细菌类型相同，种群永远不会改变。在第二个样例中，有三种可能的配置："_ab_"（无攻击）、"_aa_"（第一个菌落征服第二个菌落）和 "_bb_"（第二个菌落征服第一个菌落）。对于第三个样例的答案，请注意可以发生多次攻击。

**Definitions** Let $ n \in \mathbb{Z} $ be the number of regions. Let $ s \in \{a, \dots, z\}^n $ be the initial string representing the bacterial population. **Constraints** $ 1 \leq n \leq 5000 $ **Objective** Compute the number of distinct reachable configurations of the string under the following rules: - At most one attack occurs at a time. - An attack: a colony at position $ i $ (with character $ c $) conquers an adjacent colony at $ i+1 $ or $ i-1 $, replacing it with $ c $. - The attacking colony remains unchanged. - Attacks may occur in any sequence, including zero. The answer is the size of the set of all strings reachable from $ s $ via any sequence of such attacks, modulo $ 10^9 + 7 $.

Samples

Input #1

3
aaa

Output #1

Input #2

2
ab

Output #2

Input #3

4
babb

Output #3

Input #4

7
abacaba

Output #4

API Response (JSON)

{
  "problem": {
    "name": "D. Bacterial Melee",
    "description": {
      "content": "Julia is conducting an experiment in her lab. She placed several luminescent bacterial colonies in a horizontal testtube. Different types of bacteria can be distinguished by the color of light they em",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF759D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Julia is conducting an experiment in her lab. She placed several luminescent bacterial colonies in a horizontal testtube. Different types of bacteria can be distinguished by the color of light they em...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Julia 正在她的实验室中进行一项实验。她将若干发光的细菌菌落放置在一个水平的试管中。不同类型的细菌可以通过它们发出的光的颜色来区分。Julia 用小写拉丁字母 \"_a_\" 到 \"_z_\" 标记细菌的类型。\n\n试管被划分为 #cf_span[n] 个连续的区域。在任意时刻，每个区域都由一个特定类型细菌的菌落占据。因此，试管在任意时刻的种群可以用一个由 #cf_span[n] 个拉丁字符组成的字符...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of regions.  \nLet $ s \\in \\{a, \\dots, z\\}^n $ be the initial string representing the bacterial population.  \n\n**Constraints**  \n$ 1 \\leq n \\leq...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments