BZOJ4350 括号序列再战猪猪侠

Luogu
IDLGP10600
Time1000ms
Memory512MB
DifficultyP5
动态规划 DPO2优化区间 DP
括号序列是一个仅由 `()` 构成的序列。以下的括号序列是合法的: 1. `()` 是一个合法序列。 2. 如果 `A` 是一个合法序列,则 `(A)` 也是一个合法序列。 3. 如果 `A` 和 `B` 都是合法序列,则 `AB` 也是一个合法序列。 定义 $match_i$ 表示从左往右数第 $i$ 个左括号所对应的是第几个右括号。 现在得到了一个长度为 $2n$ 的括号序列,提供 $m$ 个信息,第 $i$ 个信息形如 $a_i,b_i$,表示 $match_{a_i}<match_{b_i}$。 现问,若根据这些信息还原出合法括号序列的方案数一共有多少?答案对 $998244353$ 取模。 ## Input 第一行一个正整数 $T$,表示数据组数。 对于每组数据,第一行两个正整数 $n,m$。其中 $n$ 表示有几个左括号,$m$ 表示信息数。 接下来 $m$ 行,每行两个正整数 $a_i,b_i$。 ## Output 对于每组数据,输出一个数表示答案。 [samples] ## Background 题目来自原 BZOJ,我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益,可联系我们。 ## Note 对于所有数据,保证 $1\leq T\leq 5$,$1\leq n\leq 300$,$1\leq a_i,b_i\leq n$。
Samples
Input #1
5
1 0
5 0
3 2
1 2
2 3
3 2
2 1
2 3
3 3
1 2
2 3
3 1
Output #1
1
42
1
2
0
API Response (JSON)
{
  "problem": {
    "name": "BZOJ4350 括号序列再战猪猪侠",
    "description": {
      "content": "括号序列是一个仅由 `()` 构成的序列。以下的括号序列是合法的: 1. `()` 是一个合法序列。 2. 如果 `A` 是一个合法序列,则 `(A)`  也是一个合法序列。 3. 如果 `A` 和 `B` 都是合法序列,则 `AB` 也是一个合法序列。 定义 $match_i$ 表示从左往右数第 $i$ 个左括号所对应的是第几个右括号。 现在得到了一个长度为 $2n$ 的括号序列,提供 $m",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10600"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "括号序列是一个仅由 `()` 构成的序列。以下的括号序列是合法的:\n1. `()` 是一个合法序列。\n2. 如果 `A` 是一个合法序列,则 `(A)`  也是一个合法序列。\n3. 如果 `A` 和 `B` 都是合法序列,则 `AB` 也是一个合法序列。\n\n定义 $match_i$ 表示从左往右数第 $i$ 个左括号所对应的是第几个右括号。\n\n现在得到了一个长度为 $2n$ 的括号序列,提供 $m...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments