C1. Dawn of the planet of the Rastas

Codeforces

IDCF10070C1

Time15000ms

Memory1024MB

Difficulty—

English · Original

Formal · Original

Due to the cruelties of Mike, Rastas attacked his country (to help its people of course) and they're moving forward to the capital. Rastas' army has 2n - 1 soldiers and the strength of soldier number i is the number of set bits (bits equal to 1) in binary representation of number i (soldiers are numbered from 1 to 2n - 1). If the greatest common divisor of numbers a and b is gcd(a, b), we know that strength of this army which we show with S is equal to: As the minister of Mike, it's your duty to calculate S modulo 109 + 7. Subtasks: Each subtask consists of one testcase. Input consists of one integer, n. Print the answer modulo 109 + 7 in a single line. ## Input Each subtask consists of one testcase.Input consists of one integer, n. ## Output Print the answer modulo 109 + 7 in a single line. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $. Let $ m = 2^n - 1 $. For $ i \in \{1, 2, \dots, m\} $, define $ s(i) = \text{popcount}(i) $, the number of 1-bits in the binary representation of $ i $. **Constraints** $ 1 \leq n \leq 10^6 $ (implied by subtask context and modulus $ 10^9 + 7 $) **Objective** Compute: $$ S = \sum_{i=1}^{2^n - 1} \sum_{j=1}^{2^n - 1} \gcd(s(i), s(j)) \cdot [\gcd(i, j) = \gcd(s(i), s(j))] $$ modulo $ 10^9 + 7 $. (Note: The condition “If $ \gcd(a, b) = \gcd(\text{popcount}(a), \text{popcount}(b)) $” implies that the sum is over pairs $ (i,j) $ where $ \gcd(i,j) = \gcd(s(i), s(j)) $, and for such pairs, the contribution is $ \gcd(s(i), s(j)) $. All other pairs contribute 0.)

API Response (JSON)

{
  "problem": {
    "name": "C1. Dawn of the planet of the Rastas",
    "description": {
      "content": "Due to the cruelties of Mike, Rastas attacked his country (to help its people of course) and they're moving forward to the capital.  Rastas' army has 2n - 1 soldiers and the strength of soldier numbe",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 15000,
      "memory_limit": 1048576
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10070C1"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Due to the cruelties of Mike, Rastas attacked his country (to help its people of course) and they're moving forward to the capital. \n\nRastas' army has 2n - 1 soldiers and the strength of soldier numbe...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $.  \nLet $ m = 2^n - 1 $.  \nFor $ i \\in \\{1, 2, \\dots, m\\} $, define $ s(i) = \\text{popcount}(i) $, the number of 1-bits in the binary representation of $ i ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments