F. Fibonacci String Subsequences

Codeforces

IDCF946F

Time3000ms

Memory256MB

Difficulty—

combinatoricsdpmatrices

English · Original

Chinese · Translation

Formal · Original

You are given a binary string _s_ (each character of this string is either _0_ or _1_). Let's denote the cost of string _t_ as the number of occurences of _s_ in _t_. For example, if _s_ is _11_ and _t_ is _111011_, then the cost of _t_ is 3. Let's also denote the Fibonacci strings sequence as follows: * _F_(0) is _0_; * _F_(1) is _1_; * _F_(_i_) = _F_(_i_ - 1) + _F_(_i_ - 2) if _i_ > 1, where + means the concatenation of two strings. Your task is to calculate the sum of costs of all subsequences of the string _F_(_x_). Since answer may be large, calculate it modulo 109 + 7. ## Input The first line contains two integers _n_ and _x_ (1 ≤ _n_ ≤ 100, 0 ≤ _x_ ≤ 100) — the length of _s_ and the index of a Fibonacci string you are interested in, respectively. The second line contains _s_ — a string consisting of _n_ characters. Each of these characters is either _0_ or _1_. ## Output Print the only integer — the sum of costs of all subsequences of the string _F_(_x_), taken modulo 109 + 7. [samples]

给你一个二进制字符串 #cf_span[s]（该字符串的每个字符要么是 _0_，要么是 _1_）。我们定义字符串 #cf_span[t] 的代价为 #cf_span[s] 在 #cf_span[t] 中出现的次数。例如，如果 #cf_span[s] 是 _11_，而 #cf_span[t] 是 _111011_，那么 #cf_span[t] 的代价为 #cf_span[3]。我们定义斐波那契字符串序列如下：你的任务是计算字符串 #cf_span[F(x)] 的所有子序列的代价之和。由于答案可能很大，请对 #cf_span[109 + 7] 取模。第一行包含两个整数 #cf_span[n] 和 #cf_span[x]（#cf_span[1 ≤ n ≤ 100]，#cf_span[0 ≤ x ≤ 100]），分别表示 #cf_span[s] 的长度和你感兴趣的斐波那契字符串的索引。第二行包含 #cf_span[s] —— 一个由 #cf_span[n] 个字符组成的字符串，每个字符要么是 _0_，要么是 _1_。输出一个整数——字符串 #cf_span[F(x)] 的所有子序列的代价之和，对 #cf_span[109 + 7] 取模。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[x]（#cf_span[1 ≤ n ≤ 100]，#cf_span[0 ≤ x ≤ 100]），分别表示 #cf_span[s] 的长度和你感兴趣的斐波那契字符串的索引。第二行包含 #cf_span[s] —— 一个由 #cf_span[n] 个字符组成的字符串，每个字符要么是 _0_，要么是 _1_。 ## Output 输出一个整数——字符串 #cf_span[F(x)] 的所有子序列的代价之和，对 #cf_span[109 + 7] 取模。 [samples]

**Definitions** Let $ s \in \{0,1\}^n $ be a binary string of length $ n $. Let $ F(x) $ denote the $ x $-th Fibonacci string, defined as: - $ F(0) = "0" $, - $ F(1) = "1" $, - $ F(x) = F(x-1) + F(x-2) $ for $ x \geq 2 $, where $ + $ denotes string concatenation. Let $ \mathcal{S}(t) $ denote the set of all subsequences of a string $ t $. Let $ \text{cost}(s, t) = $ number of occurrences of $ s $ as a subsequence in $ t $. **Constraints** 1. $ 1 \leq n \leq 100 $ 2. $ 0 \leq x \leq 100 $ 3. $ s \in \{0,1\}^n $ **Objective** Compute: $$ \sum_{t \in \mathcal{S}(F(x))} \text{cost}(s, t) \mod (10^9 + 7) $$

Samples

Input #1

2 4
11

Output #1

Input #2

10 100
1010101010

Output #2

553403224

API Response (JSON)

{
  "problem": {
    "name": "F. Fibonacci String Subsequences",
    "description": {
      "content": "You are given a binary string _s_ (each character of this string is either _0_ or _1_). Let's denote the cost of string _t_ as the number of occurences of _s_ in _t_. For example, if _s_ is _11_ and ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF946F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a binary string _s_ (each character of this string is either _0_ or _1_).\n\nLet's denote the cost of string _t_ as the number of occurences of _s_ in _t_. For example, if _s_ is _11_ and ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给你一个二进制字符串 #cf_span[s]（该字符串的每个字符要么是 _0_，要么是 _1_）。\n\n我们定义字符串 #cf_span[t] 的代价为 #cf_span[s] 在 #cf_span[t] 中出现的次数。例如，如果 #cf_span[s] 是 _11_，而 #cf_span[t] 是 _111011_，那么 #cf_span[t] 的代价为 #cf_span[3]。\n\n我们定义斐波那...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{0,1\\}^n $ be a binary string of length $ n $.  \nLet $ F(x) $ denote the $ x $-th Fibonacci string, defined as:  \n- $ F(0) = \"0\" $,  \n- $ F(1) = \"1\" $,  \n- $ F(x) = F(x-...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments