G. Palindrome Partition

Codeforces

IDCF932G

Time3000ms

Memory256MB

Difficulty—

dpstring suffix structuresstrings

English · Original

Chinese · Translation

Formal · Original

Given a string _s_, find the number of ways to split _s_ to substrings such that if there are _k_ substrings (_p_1, _p_2, _p_3, ..., _p__k_) in partition, then _p__i_ = _p__k_ - _i_ + 1 for all _i_ (1 ≤ _i_ ≤ _k_) and _k_ is even. Since the number of ways can be large, print it modulo 109 + 7. ## Input The only line of input contains a string _s_ (2 ≤ |_s_| ≤ 106) of even length consisting of lowercase Latin letters. ## Output Print one integer, the number of ways of partitioning the string modulo 109 + 7. [samples] ## Note In the first case, the only way to partition the string is _ab_|_cd_|_cd_|_ab_. In the second case, the string can be partitioned as _ab_|_b_|_ab_|_ab_|_ab_|_ab_|_b_|_ab_ or _ab_|_b_|_abab_|_abab_|_b_|_ab_ or _abbab_|_ab_|_ab_|_abbab_.

给定一个字符串 #cf_span[s]，求将 #cf_span[s] 分割为若干子串的方案数，使得若分割后有 #cf_span[k] 个子串 #cf_span[(p1, p2, p3, ..., pk)]，则对所有 #cf_span[i] #cf_span[(1 ≤ i ≤ k)] 都满足 #cf_span[pi = pk - i + 1]，且 #cf_span[k] 为偶数。由于方案数可能很大，请对 #cf_span[109 + 7] 取模输出。输入仅一行，包含一个长度为偶数的字符串 #cf_span[s] #cf_span[(2 ≤ |s| ≤ 106)]，由小写拉丁字母组成。请输出一个整数，表示将字符串分割的方案数对 #cf_span[109 + 7] 取模的结果。在第一个例子中，分割字符串的唯一方式是 #cf_span[ab|cd|cd|ab]。在第二个例子中，字符串可以被分割为 #cf_span[ab|b|ab|ab|ab|ab|b|ab] 或 #cf_span[ab|b|abab|abab|b|ab] 或 #cf_span[abbab|ab|ab|abbab]。 ## Input 输入仅一行，包含一个长度为偶数的字符串 #cf_span[s] #cf_span[(2 ≤ |s| ≤ 106)]，由小写拉丁字母组成。 ## Output 请输出一个整数，表示将字符串分割的方案数对 #cf_span[109 + 7] 取模的结果。 [samples] ## Note 在第一个例子中，分割字符串的唯一方式是 #cf_span[ab|cd|cd|ab]。在第二个例子中，字符串可以被分割为 #cf_span[ab|b|ab|ab|ab|ab|b|ab] 或 #cf_span[ab|b|abab|abab|b|ab] 或 #cf_span[abbab|ab|ab|abbab]。

**Definitions** Let $ s \in \Sigma^* $ be a string of even length $ n = |s| $, where $ \Sigma $ is the set of lowercase Latin letters. Let $ k \in 2\mathbb{Z}^+ $ be an even positive integer. A partition of $ s $ into $ k $ non-empty contiguous substrings $ (p_1, p_2, \dots, p_k) $ is called *palindromic-symmetric* if $ p_i = p_{k - i + 1} $ for all $ i \in \{1, 2, \dots, k\} $. **Constraints** 1. $ 2 \leq n \leq 10^6 $ 2. $ n $ is even. 3. Each substring $ p_i $ is non-empty and contiguous. 4. The partition must satisfy $ p_i = p_{k - i + 1} $ for all $ i $, and $ k $ is even. **Objective** Count the number of palindromic-symmetric partitions of $ s $, modulo $ 10^9 + 7 $.

Samples

Input #1

abcdcdab

Output #1

Input #2

abbababababbab

Output #2

API Response (JSON)

{
  "problem": {
    "name": "G. Palindrome Partition",
    "description": {
      "content": "Given a string _s_, find the number of ways to split _s_ to substrings such that if there are _k_ substrings (_p_1, _p_2, _p_3, ..., _p__k_) in partition, then _p__i_ = _p__k_ - _i_ + 1 for all _i_ (1",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF932G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given a string _s_, find the number of ways to split _s_ to substrings such that if there are _k_ substrings (_p_1, _p_2, _p_3, ..., _p__k_) in partition, then _p__i_ = _p__k_ - _i_ + 1 for all _i_ (1...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个字符串 #cf_span[s]，求将 #cf_span[s] 分割为若干子串的方案数，使得若分割后有 #cf_span[k] 个子串 #cf_span[(p1, p2, p3, ..., pk)]，则对所有 #cf_span[i] #cf_span[(1 ≤ i ≤ k)] 都满足 #cf_span[pi = pk - i + 1]，且 #cf_span[k] 为偶数。\n\n由于方案数可能很...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\Sigma^* $ be a string of even length $ n = |s| $, where $ \\Sigma $ is the set of lowercase Latin letters.  \nLet $ k \\in 2\\mathbb{Z}^+ $ be an even positive integer.  \nA ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments