[ICPC 2022 Xi'an R] Square Grid

Luogu

IDLGP9366

Time4000ms

Memory512MB

DifficultyP7

2022O2优化ICPC西安

Given a square grid, its lattice points labeled from $(0, 0)$ to $(n, n)$, and a number $t$. You need to answer $q$ queries in this format: given $A = (x_0, y_0)$ and $B = (x_1, y_1)$, how many ways are there to move from $A$ to $B$ in exactly $t$ steps so that in each step you move from a lattice point to one of its neighbors (up, down, left, right). Calculate the answer modulo $998\,244\,353$. ## Input The first line contains three integers $n$ ($1 \leq n \leq 10^5$), $t$ ($1 \leq t \leq 10^9$) and $q$ ($1 \leq q \leq 3 \times 10^5$). Each of the following $q$ lines contains four integers $x_0$, $y_0$, $x_1$ and $y_1$ ($0 \leq x_0, y_0, x_1, y_1 \leq n$), representing a query. ## Output For each query, output a line containing one integer, representing the answer to the query modulo $998\,244\,353$. [samples] ## Note **Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem I. **Author**: djq_cpp.

Samples

Input #1

Output #1

30
64
0

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[ICPC 2022 Xi'an R] Square Grid",
    "description": {
      "content": "Given a square grid, its lattice points labeled from $(0, 0)$ to $(n, n)$, and a number $t$. You need to answer $q$ queries in this format: given $A = (x_0, y_0)$ and $B = (x_1, y_1)$, how many ways ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9366"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given a square grid, its lattice points labeled from $(0, 0)$ to $(n, n)$, and a number $t$.\n\nYou need to answer $q$ queries in this format: given $A = (x_0, y_0)$ and $B = (x_1, y_1)$, how many ways ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments