B. Black and White

Codeforces

IDCF10247B

Time1000ms

Memory256MB

Difficulty—

_Master Pang_ walks from the bottom-left corner of a $n times m$ chessboard to the top-right corner. The chessboard contains $n + 1$ horizontal line segments and $m + 1$ vertical line segments. The horizontal line segments are numbered from $0$ to $n$ from bottom to top and the vertical ones are numbered from $0$ to $m$ from left to right. The intersection of horizontal line segment $r$ and vertical segment $c$ is denoted by $(r, c)$. The bottom-left corner is $(0, 0)$ and the top-right corner is $(n, m)$. At each step, he can only walk from $(x, y)$ to $(x, y + 1)$ or from $(x, y)$ to $(x + 1, y)$. Each of the $n times m$ cells is colored white or black. A cell with corners $(i, j), (i + 1, j), (i, j + 1), (i + 1, j + 1)$ $(0 <= i < n, 0 <= j < m)$ is colored white if and only if $i equiv j pmod 2$. Given $P a n g$'s walking path from $(0, 0)$ to $(n, m)$, his score is $a -b$ where $a$ is the number of white cells to the left of his walking path and $b$ is the number of black cells to the left of his walking path. Help _Master Pang_ count the number of walking paths with score $k$ modulo $998244353$. The first line contains a single integer $T$ — the number of test cases ($1 <= T <= 100$). Each of the next $T$ lines contains three integers $n$, $m$ and $k$ ($1 <= n <= 100000, 1 <= m <= 100000, -100000 <= k <= 100000$). For each test case, output a single integer — the answer modulo $998244353$. ## Input The first line contains a single integer $T$ — the number of test cases ($1 <= T <= 100$).Each of the next $T$ lines contains three integers $n$, $m$ and $k$ ($1 <= n <= 100000, 1 <= m <= 100000, -100000 <= k <= 100000$). ## Output For each test case, output a single integer — the answer modulo $998244353$. [samples]

API Response (JSON)

{
  "problem": {
    "name": "B. Black and White",
    "description": {
      "content": "_Master Pang_ walks from the bottom-left corner of a $n times m$ chessboard to the top-right corner. The chessboard contains $n + 1$ horizontal line segments and $m + 1$ vertical line segments. The ho",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10247B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_Master Pang_ walks from the bottom-left corner of a $n times m$ chessboard to the top-right corner. The chessboard contains $n + 1$ horizontal line segments and $m + 1$ vertical line segments. The ho...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments