G. New Year and Binary Tree Paths

Codeforces

IDCF750G

Time3000ms

Memory256MB

Difficulty—

bitmasksbrute forcecombinatoricsdp

English · Original

Chinese · Translation

Formal · Original

The New Year tree is an infinite perfect binary tree rooted in the node 1. Each node _v_ has two children: nodes indexed (2·_v_) and (2·_v_ + 1). <center>![image](https://espresso.codeforces.com/2b690afc27817c4127489b6235f46a6704dcf150.png)</center>Polar bears love decorating the New Year tree and Limak is no exception. As he is only a little bear, he was told to decorate only one simple path between some pair of nodes. Though he was given an opportunity to pick the pair himself! Now he wants to know the number of unordered pairs of indices (_u_, _v_) (_u_ ≤ _v_), such that the sum of indices of all nodes along the simple path between _u_ and _v_ (including endpoints) is equal to _s_. Can you help him and count this value? ## Input The only line of the input contains a single integer _s_ (1 ≤ _s_ ≤ 1015). ## Output Print one integer, denoting the number of unordered pairs of nodes indices defining simple paths with the sum of indices of vertices equal to _s_. [samples] ## Note In sample test, there are 4 paths with the sum of indices equal to 10: <center>![image](https://espresso.codeforces.com/1c10ece7b5b332a215774a7c3aef1a84903dd7c9.png)</center>

[{"iden":"statement","content":"新年树是一棵以节点 #cf_span[1] 为根的无限完美二叉树。每个节点 #cf_span[v] 有两个子节点：编号为 #cf_span[(2·v)] 和 #cf_span[(2·v + 1)] 的节点。\n\n北极熊喜欢装饰新年树，Limak 也不例外。由于他只是一只小熊，他被要求只装饰一对节点之间的简单路径。不过，他有机会自己选择这对节点！现在他想知道，有多少个无序的节点对编号 #cf_span[(u, v)]（#cf_span[u ≤ v]），使得从 #cf_span[u] 到 #cf_span[v] 的简单路径上所有节点的编号之和（包括端点）恰好等于 #cf_span[s]？你能帮他计算这个值吗？\n\n输入仅包含一行，一个整数 #cf_span[s]（#cf_span[1 ≤ s ≤ 1015]）。\n\n请输出一个整数，表示节点编号构成的无序对的数量，这些对定义的简单路径上所有节点编号之和等于 #cf_span[s]。\n\n在样例测试中，有 #cf_span[4] 条路径的节点编号之和等于 #cf_span[10]：\n\n"},{"iden":"input","content":"输入仅包含一行，一个整数 #cf_span[s]（#cf_span[1 ≤ s ≤ 1015]）。"},{"iden":"output","content":"请输出一个整数，表示节点编号构成的无序对的数量，这些对定义的简单路径上所有节点编号之和等于 #cf_span[s]。"},{"iden":"note","content":"在样例测试中，有 #cf_span[4] 条路径的节点编号之和等于 #cf_span[10]： "}] ### 说明： - 所有数学表达式如 `#cf_span[s]`、`#cf_span[1 ≤ s ≤ 1015]` 等均原样保留，未做任何转义或美化。 - “unordered pairs” → “无序对” - “simple path” → “简单路径” - “sum of indices” → “编号之和” - “including endpoints” → “包括端点” - 保持原文段落结构与换行符。 - 输出为严格合法 JSON 数组，字段名与输入一致。

**Definitions** Let $ T $ be the infinite perfect binary tree with root $ 1 $, where each node $ v $ has children $ 2v $ and $ 2v+1 $. Let $ P(u, v) $ denote the set of nodes on the unique simple path between nodes $ u $ and $ v $, for $ u \leq v $. Let $ S(u, v) = \sum_{w \in P(u, v)} w $ be the sum of node indices along the path. **Constraints** $ 1 \leq s \leq 10^{15} $ **Objective** Count the number of unordered pairs $ (u, v) $ with $ u \leq v $ such that $ S(u, v) = s $.

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "G. New Year and Binary Tree Paths",
    "description": {
      "content": "The New Year tree is an infinite perfect binary tree rooted in the node 1. Each node _v_ has two children: nodes indexed (2·_v_) and (2·_v_ + 1). <center>![image](https://espresso.codeforces.com/2b69",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF750G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The New Year tree is an infinite perfect binary tree rooted in the node 1. Each node _v_ has two children: nodes indexed (2·_v_) and (2·_v_ + 1).\n\n<center>![image](https://espresso.codeforces.com/2b69...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"新年树是一棵以节点 #cf_span[1] 为根的无限完美二叉树。每个节点 #cf_span[v] 有两个子节点：编号为 #cf_span[(2·v)] 和 #cf_span[(2·v + 1)] 的节点。\\n\\n北极熊喜欢装饰新年树，Limak 也不例外。由于他只是一只小熊，他被要求只装饰一对节点之间的简单路径。不过，他有机会自己选...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T $ be the infinite perfect binary tree with root $ 1 $, where each node $ v $ has children $ 2v $ and $ 2v+1 $.  \nLet $ P(u, v) $ denote the set of nodes on the unique simple ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments