H. Log Concave Sequences

Codeforces

IDCF10230H

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

A sequence of numbers A is said to be logarithm concave if, and only if, for every 2 ≤ i ≤ n - 1, ai - 1 * ai + 1 ≤ ai2. For example the sequence A = (1, 2, 3) is logarithm concave. The sequence A = (2, 2, 3) is not logarithm concave. In this problem, you will have to answer what is the number of log concave sequences which contain only the numbers 0, 1 or 2, with N elements. As this number could be very large, print the answer mod 109 + 7. The input consists of a single integer N (3 ≤ N ≤ 1018) indicating the size of the log concave sequence. One integer with the number of log concave sequences with size N that contains only the numbers 0, 1 or 2. ## Input The input consists of a single integer N (3 ≤ N ≤ 1018) indicating the size of the log concave sequence. ## Output One integer with the number of log concave sequences with size N that contains only the numbers 0, 1 or 2. [samples]

**Definitions** Let $ A, B \in \mathbb{Z} $ with $ 1 \leq A, B \leq 28 $. Let $ O_1, O_2, O_3 \in \Sigma^A $ be the strings of the three Owls members, where $ \Sigma = \{ \text{'A'}, \text{'B'}, \dots, \text{'Z'} \} $. Let $ G_1, G_2, G_3 \in \Sigma^B $ be the strings of the three Goats members. For a string $ S \in \Sigma^n $, define the score: $$ \text{score}(S) = \left( \sum_{i=1}^{n} \text{val}(S[i]) \right) \mod M, \quad \text{where } M = 10^{15} + 37, \quad \text{val}(c) = \text{ASCII}(c) $$ **Constraints** For each position $ i \in \{1, \dots, A\} $, the Owls' resulting string $ S_O $ must satisfy: $$ S_O[i] \in \{ O_1[i], O_2[i], O_3[i] \} $$ For each position $ i \in \{1, \dots, B\} $, the Goats' resulting string $ S_G $ must satisfy: $$ S_G[i] \in \{ G_1[i], G_2[i], G_3[i] \} $$ **Objective** Minimize $ \text{score}(S_O) $ over all valid $ S_O \in \Sigma^A $, and minimize $ \text{score}(S_G) $ over all valid $ S_G \in \Sigma^B $. Compare the minimal scores: - If $ \min \text{score}(S_O) < \min \text{score}(S_G) $, output "Owls" - If $ \min \text{score}(S_O) > \min \text{score}(S_G) $, output "Goats" - If $ \min \text{score}(S_O) = \min \text{score}(S_G) $, output "Tie"

API Response (JSON)

{
  "problem": {
    "name": "H. Log Concave Sequences",
    "description": {
      "content": "A sequence of numbers A is said to be logarithm concave if, and only if, for every 2 ≤ i ≤ n - 1, ai - 1 * ai + 1 ≤ ai2. For example the sequence A = (1, 2, 3) is logarithm concave. The sequence A = ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10230H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A sequence of numbers A is said to be logarithm concave if, and only if, for every 2 ≤ i ≤ n - 1, ai - 1 * ai + 1 ≤ ai2.\n\nFor example the sequence A = (1, 2, 3) is logarithm concave. The sequence A = ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ A, B \\in \\mathbb{Z} $ with $ 1 \\leq A, B \\leq 28 $.  \nLet $ O_1, O_2, O_3 \\in \\Sigma^A $ be the strings of the three Owls members, where $ \\Sigma = \\{ \\text{'A'}, \\text{'B'}, \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments