[ICPC 2024 Xi'an I] Yet Another Maximum Matching Counting Problem

Luogu

IDLGP10563

Time3000ms

Memory512MB

DifficultyP7

2024O2优化ICPC西安

There is a two-dimensional plane. You have a set of points $\{(x_i,y_i)\}$ that satisfies $1\le x_i\le n, 1\le y_i\le m$ (Both $x_i$ and $y_i$ are integers), and there are no two points with the same coordinates. If two points have the same horizontal or vertical coordinates, we will connect an edge between these two points. This forms a graph. You need to find the sum of the maximum number of matches in the graphs formed by all possible $2^{nm}-1$ non empty sets, and output the result modulo $998244353$. Here, the maximum number of matches in a graph is defined as: selecting the most edges so that there are no common vertices between any two edges. ## Input There are multiple testcases in this problem. The first line contains an integer $T(1\le T\le 100)$, which represents the number of testcases. Each of the testcases contains two integers $n,m(1\leq n,m\leq 500)$. ## Output For each of the testcases, print an integer representing the result modulo $998244353$. [samples]

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[ICPC 2024 Xi'an I] Yet Another Maximum Matching Counting Problem",
    "description": {
      "content": "There is a two-dimensional plane.                You have a set of points $\\{(x_i,y_i)\\}$ that satisfies $1\\le x_i\\le n, 1\\le y_i\\le m$ (Both $x_i$ and $y_i$ are integers), and there are no two points",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10563"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a two-dimensional plane.\n    \n    \n    \nYou have a set of points $\\{(x_i,y_i)\\}$ that satisfies $1\\le x_i\\le n, 1\\le y_i\\le m$ (Both $x_i$ and $y_i$ are integers), and there are no two points...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments