C. Fibonacci

Codeforces

IDCF10264C

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Find the $n$-th Fibonacci number modulo $10^9 + 7$. So, you need to find $F_n$ in the sequence defined as $F_0 = 0$, $F_1 = 1$ and $F_i = F_{i -1} + F_{i -2}$ for $i >= 2$. An integer $n$ ($0 <= n <= 10^(18)$). Print the answer modulo $1000000007$. The first few terms of Fibonacci sequence are $(0, 1, 1, 2, 3, 5, 8, 13, \\dots)$. In particular, we have $F_0 = 0$, $F_3 = 2$ and $F_6 = 8$. And for the last sample test: $$F_{50} = 12586269025 \equiv 586268941 \pmod {10^9 + 7}$$ ## Input An integer $n$ ($0 <= n <= 10^(18)$). ## Output Print the answer modulo $1000000007$. [samples] ## Note The first few terms of Fibonacci sequence are $(0, 1, 1, 2, 3, 5, 8, 13, \\dots)$. In particular, we have $F_0 = 0$, $F_3 = 2$ and $F_6 = 8$. And for the last sample test:$$F_{50} = 12586269025 \equiv 586268941 \pmod {10^9 + 7}$$

**Definitions** Let $ n \in \mathbb{Z} $ be the number of notes in the song, $ k \in \mathbb{Z} $ the number of chords. Let $ S = (s_{i,j}) \in \mathbb{R}^{k \times k} $ be the transition time matrix, where $ s_{i,j} $ is the direct time to switch from chord $ i $ to chord $ j $, with $ s_{i,i} = 0 $. Let $ C = (c_1, c_2, \dots, c_n) \in \{1, \dots, k\}^n $ be the sequence of chords in the song. Let $ D = (d_{i,j}) \in \mathbb{R}^{k \times k} $ be the shortest-path transition matrix computed via Floyd-Warshall: $$ d_{i,j} = \min_{\text{paths } i \to j} \sum \text{edge weights} $$ **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ 1 \leq k \leq 100 $ 3. $ 1 \leq s_{i,j} \leq 10^9 $ for all $ i,j \in \{1,\dots,k\} $ 4. $ s_{i,i} = 0 $ for all $ i $ 5. The song sequence $ C $ is fixed except for **at most one** chord that may be changed to any other chord in $ \{1,\dots,k\} $. **Objective** Compute the minimum total time to play the song, where: - Base time (without any change): $$ T_0 = \sum_{i=1}^{n-1} d_{c_i, c_{i+1}} $$ - For each position $ p \in \{1, \dots, n\} $ and each possible replacement chord $ x \in \{1, \dots, k\} $, define: - If $ p = 1 $: $ T_p^x = d_{x, c_2} + \sum_{i=2}^{n-1} d_{c_i, c_{i+1}} $ - If $ p = n $: $ T_p^x = d_{c_{n-1}, x} + \sum_{i=1}^{n-2} d_{c_i, c_{i+1}} $ - If $ 1 < p < n $: $ T_p^x = d_{c_{p-1}, x} + d_{x, c_{p+1}} + \sum_{\substack{i=1 \\ i \neq p-1, p}}^{n-1} d_{c_i, c_{i+1}} $ - Let $ T_{\text{min}} = \min\left( T_0,\ \min_{p \in \{1,\dots,n\},\ x \in \{1,\dots,k\}} T_p^x \right) $ **Output** $ T_{\text{min}} $

API Response (JSON)

{
  "problem": {
    "name": "C. Fibonacci",
    "description": {
      "content": "Find the $n$-th Fibonacci number modulo $10^9 + 7$. So, you need to find $F_n$ in the sequence defined as $F_0 = 0$, $F_1 = 1$ and $F_i = F_{i -1} + F_{i -2}$ for $i >= 2$. An integer $n$ ($0 <= n <",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10264C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Find the $n$-th Fibonacci number modulo $10^9 + 7$.\n\nSo, you need to find $F_n$ in the sequence defined as $F_0 = 0$, $F_1 = 1$ and $F_i = F_{i -1} + F_{i -2}$ for $i >= 2$.\n\nAn integer $n$ ($0 <= n <...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of notes in the song, $ k \\in \\mathbb{Z} $ the number of chords.  \nLet $ S = (s_{i,j}) \\in \\mathbb{R}^{k \\times k} $ be the transition time mat...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments