Distance on Large Perfect Binary Tree

AtCoder

IDabc220_e

Time2000ms

Memory256MB

Difficulty—

We have a tree with $2^N-1$ vertices. The vertices are numbered $1$ through $2^N-1$. For each $1\leq i < 2^{N-1}$, the following edges exist: * an undirected edge connecting Vertex $i$ and Vertex $2i$, * an undirected edge connecting Vertex $i$ and Vertex $2i+1$. There is no other edge. Let the distance between two vertices be the number of edges in the simple path connecting those two vertices. Find the number, modulo $998244353$, of pairs of vertices $(i, j)$ such that the distance between them is $D$. ## Constraints * $2 \leq N \leq 10^6$ * $1 \leq D \leq 2\times 10^6$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $D$ [samples]

Samples

Input #1

3 2

Output #1

14

The following figure describes the given tree.
![image](https://img.atcoder.jp/ghi/86d098048a50638decb39ed6659d32cf.png)
There are $14$ pairs of vertices such that the distance between them is $2$: $(1,4),(1,5),(1,6),(1,7),(2,3),(3,2),(4,1),(4,5),(5,1),(5,4),(6,1),(6,7),(7,1),(7,6)$.

Input #2

14142 17320

Output #2

11284501

API Response (JSON)

{
  "problem": {
    "name": "Distance on Large Perfect Binary Tree",
    "description": {
      "content": "We have a tree with $2^N-1$ vertices.   The vertices are numbered $1$ through $2^N-1$. For each $1\\leq i < 2^{N-1}$, the following edges exist: *   an undirected edge connecting Vertex $i$ and Vertex",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc220_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have a tree with $2^N-1$ vertices.  \nThe vertices are numbered $1$ through $2^N-1$. For each $1\\leq i < 2^{N-1}$, the following edges exist:\n\n*   an undirected edge connecting Vertex $i$ and Vertex...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments