D. Magic Strings

Codeforces

IDCF10235D

Time4000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Consider the sequence of strings $F_1, F_2, \\dots$, defined as: $$ F_1 = ab\text{,} $$ $$ F_{k+1} = F_kF_kb\text{.} $$ Calculate the number of distinct _subsequences_ of the string $F_n$ modulo $10^9 + 7$. The first line of input contains a single integer $t$ ($1 <= t <= 10$), which is the number of test cases. The second line of input contains $t$ integers $n$ ($1 <= n <= 10^(18)$), one for each test case. For each test case, output the single integer which is the answer to the problem. Separate consecutive answers by single spaces. The first three strings are: $F_1 = texttt(a b)$, $F_2 = texttt(a b a b b)$, and $F_3 = texttt(a b a b b a b a b b b)$. ## Input The first line of input contains a single integer $t$ ($1 <= t <= 10$), which is the number of test cases.The second line of input contains $t$ integers $n$ ($1 <= n <= 10^(18)$), one for each test case. ## Output For each test case, output the single integer which is the answer to the problem. Separate consecutive answers by single spaces. [samples] ## Note The first three strings are: $F_1 = texttt(a b)$, $F_2 = texttt(a b a b b)$, and $F_3 = texttt(a b a b b a b a b b b)$.

**Definitions** Let $ F_1 = "ab" $, and for $ k \geq 1 $, define $ F_{k+1} = F_k F_k b $. Let $ s_n = |F_n| $ denote the length of $ F_n $, and let $ a_n $ denote the number of distinct subsequences of $ F_n $. **Constraints** 1. $ 1 \leq t \leq 10 $ 2. For each test case, $ 1 \leq n \leq 10^{18} $ **Recurrence** Let $ a_n $ be the number of distinct subsequences of $ F_n $. Then: - $ a_1 = 4 $ (subsequences of "ab": "", "a", "b", "ab") - For $ n \geq 1 $: $$ a_{n+1} = 2a_n + 1 $$ **Objective** For each test case with input $ n $, compute $ a_n \mod (10^9 + 7) $.

API Response (JSON)

{
  "problem": {
    "name": "D. Magic Strings",
    "description": {
      "content": "Consider the sequence of strings $F_1, F_2, \\\\dots$, defined as: $$ F_1 = ab\\text{,} $$ $$ F_{k+1} = F_kF_kb\\text{.} $$ Calculate the number of distinct _subsequences_ of the string $F_n$ modulo $10",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10235D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Consider the sequence of strings $F_1, F_2, \\\\dots$, defined as:\n\n$$ F_1 = ab\\text{,} $$ $$ F_{k+1} = F_kF_kb\\text{.} $$\n\nCalculate the number of distinct _subsequences_ of the string $F_n$ modulo $10...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ F_1 = \"ab\" $, and for $ k \\geq 1 $, define $ F_{k+1} = F_k F_k b $.  \nLet $ s_n = |F_n| $ denote the length of $ F_n $, and let $ a_n $ denote the number of distinct subsequenc...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments