J. Color the blocks

Codeforces

IDCF10280J

Time1000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Given you an $N * N$ grid graph,you can color any block black or white,but you have to meet the condition: For each block $(x, y)$,it can't be the same color as $(x -3, y), (x -1, y + 2), (x + 1, y + 2), (x + 3, y)$. You need to calculate the total number of options for coloring the $N * N$ grid graph. There are $T$ test cases in this problem. The first line has one integer $T (1 <= T <= 10^5)$. For every test case,the first line has $1$ integer $N (1 <= N <= 10^9)$. For every test case, output the answer in a line. ## Input There are $T$ test cases in this problem.The first line has one integer $T (1 <= T <= 10^5)$.For every test case,the first line has $1$ integer $N (1 <= N <= 10^9)$. ## Output For every test case, output the answer in a line. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of nodes. Let $ T = (V, E) $ be a rooted tree with $ V = \{1, 2, \dots, n\} $, where node $ 1 $ is the root, and for $ i = 2, \dots, n $, node $ f_i $ is the parent of node $ i $. For each node $ i \in V $, define values $ a_i, b_i \in \mathbb{R}^+ $, with $ a_1 = b_1 = 0 $. Let $ S \subseteq V $ be the set of nodes that have received a jingle bell. Initially, $ S = \{1\} $. At each step, a node $ v \notin S $ may be added to $ S $ only if its parent $ u \in S $ and $ (u,v) \in E $. When adding node $ v $ to $ S $, the beauty gain is: $$ b_v \cdot \sum_{j \notin S} a_j $$ **Constraints** 1. $ 1 \le n \le 100000 $ 2. $ 1 \le f_i < i $ for $ i = 2, \dots, n $ 3. $ 0 < a_i, b_i \le 10000 $ for all $ i $, and $ a_1 = b_1 = 0 $ **Objective** Maximize the total beauty value obtained over all $ n $ steps, starting from $ S = \{1\} $, and adding one node at a time under the parent-child constraint, until $ S = V $.

API Response (JSON)

{
  "problem": {
    "name": "J. Color the blocks",
    "description": {
      "content": "Given you an $N * N$ grid graph,you can color any block black or white,but you have to meet the condition: For each block $(x, y)$,it can't be the same color as $(x -3, y), (x -1, y + 2), (x + 1, y +",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10280J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given you an $N * N$ grid graph,you can color any block black or white,but you have to meet the condition:\n\nFor each block $(x, y)$,it can't be the same color as $(x -3, y), (x -1, y + 2), (x + 1, y +...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of nodes.  \nLet $ T = (V, E) $ be a rooted tree with $ V = \\{1, 2, \\dots, n\\} $, where node $ 1 $ is the root, and for $ i = 2, \\dots, n $, n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments