【MX-S1-T3】电动力学

Luogu

IDLGP10674

Time3000ms

Memory1024MB

DifficultyP6

动态规划 DP数学O2优化树形 DP双连通分量组合数学圆方树梦熊比赛

给定一张包含 $n$ 个点 $m$ 条边的简单无向连通图，点的编号为 $1\sim n$。你需要求出有多少集合对 $S,T\sube \{1,2,\dots,n\}$，满足对于任意的 $i\in S$，要么 $i$ 也 $\in T$，要么存在 $x,y\in T$（$x\neq y$），满足存在一条从 $x$ 到 $y$ 的简单路径经过 $i$。注意，集合对 $S,T$ 可以为空集。输出答案对 $998244353$ 取模后的结果。 ## Input 第一行两个正整数 $n,m$。接下来 $m$ 行，每行两个正整数 $u_i,v_i$，描述图上的一条边。保证图连通，无自环、重边。 ## Output 共一行一个整数，表示满足题目条件的集合对 $S,T$ 的数量对 $998244353$ 取模后的结果。 [samples] ## Background 原题链接：<https://oier.team/problems/S1C>。 ## Note __【样例解释 1】__ 所有合法的集合 $S,T$ 为： 1. $S=\{\},T=\{\}$。 2. $S=\{\},T=\{1\}$。 3. $S=\{\},T=\{2\}$。 4. $S=\{\},T=\{1,2\}$。 5. $S=\{1\},T=\{1\}$。 6. $S=\{1\},T=\{1,2\}$。 7. $S=\{2\},T=\{2\}$。 8. $S=\{2\},T=\{1,2\}$。 9. $S=\{1,2\},T=\{1,2\}$。 __【数据范围】__ __本题使用子任务捆绑测试。__ 对于 $100\%$ 的数据，$2\le n\le 5\times 10^5$，$n-1\le m\le 10^6$，$1\le u_i,v_i\le n$。保证图连通，无自环、重边。 | 子任务编号 | $n\le $ | $m\le $ | 特殊性质 | 分值 | | ---------- | -------------- | ------------------ | --------------- | ---- | | $1$ | $10$ | $\frac{n(n-1)}{2}$ | 无 | $10$ | | $2$ | $20$ | $\frac{n(n-1)}{2}$ | 无 | $10$ | | $3$ | $5\times 10^5$ | $n-1$ | $u_i=i,v_i=i+1$ | $10$ | | $4$ | $5\times 10^5$ | $n-1$ | 无 | $20$ | | $5$ | $5\times 10^5$ | $n$ | 无 | $20$ | | $6$ | $5\times 10^5$ | $10^6$ | 无 | $30$ |

Samples

Input #1

2 1
1 2

Output #1

Input #2

Output #2

Input #3

Output #3

211240350

API Response (JSON)

{
  "problem": {
    "name": "【MX-S1-T3】电动力学",
    "description": {
      "content": "给定一张包含 $n$ 个点 $m$ 条边的简单无向连通图，点的编号为 $1\\sim n$。 你需要求出有多少集合对 $S,T\\sube \\{1,2,\\dots,n\\}$，满足对于任意的 $i\\in S$，要么 $i$ 也 $\\in T$，要么存在 $x,y\\in T$（$x\\neq y$），满足存在一条从 $x$ 到 $y$ 的简单路径经过 $i$。 注意，集合对 $S,T$ 可以为空集。 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10674"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一张包含 $n$ 个点 $m$ 条边的简单无向连通图，点的编号为 $1\\sim n$。\n\n你需要求出有多少集合对 $S,T\\sube \\{1,2,\\dots,n\\}$，满足对于任意的 $i\\in S$，要么 $i$ 也 $\\in T$，要么存在 $x,y\\in T$（$x\\neq y$），满足存在一条从 $x$ 到 $y$ 的简单路径经过 $i$。\n\n注意，集合对 $S,T$ 可以为空集。\n\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments