#P15254. [2026队内训练]集合计数

    ID: 14470 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2000提高排列构造独立集双射计数添加哨兵DAG 动态规划

[2026队内训练]集合计数

题目描述

给定一张 nn 个顶点的无向图 G=(V,E)G=(V,E),顶点编号为 1,…,n1,\ldots,n。它可以由某个 1,…,n1,\ldots,n 的排列 pp 生成。对于任意 i<ji<j,顶点 i,ji,j 之间有边当且仅当 pi>pjp_i>p_j。输入直接给出图的边,排列不作为输入。

点集 A⊆VA\subseteq V 是独立集,当且仅当 AA 中任意两个不同顶点均不相邻。它是支配集,当且仅当 AA 以外的每个顶点至少与 AA 中一个顶点相邻。

求同时是独立集与支配集的点集数量,对 998244353998244353 取模。

输入格式

第一行两个整数 n,mn,m。接下来 mm 行,每行两个整数 u,vu,v,表示一条无向边。保证图由上述方式生成。

输出格式

一行一个非负整数,表示答案对 998244353998244353 取模的结果。

样例

5 7
2 5
1 5
3 5
2 3
4 1
4 3
4 2
3

图对应排列 [3,5,4,1,2][3,5,4,1,2]。三个独立支配集是 {1,2}\{1,2\}、{1,3}\{1,3\}、{4,5}\{4,5\}。

数据范围

1≤n≤1001\le n\le100,0≤m≤n(n−1)/20\le m\le n(n-1)/2。原 PDF 将 mm 的下界写为 11,本站评测包含无边图。

原子任务 分值 附加限制
1 20 n≤20n\le20
2 n≤40n\le40
3 60 无

原 PDF 题面