P4426 [HNOI/AHOI2018]毒瘤

    • 161通过
    • 648提交
  • 题目提供者 M_sea
  • 评测方式 云端评测
  • 标签 并查集 枚举,暴力 虚树 各省省选 2018 安徽 湖南 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    从前有一名毒瘤。

    毒瘤最近发现了量产毒瘤题的奥秘。考虑如下类型的数据结构题:给出一个数组,要求支持若干种奇奇怪怪的修改操作(比如区间加一个数,或者区间开平方),并支持询问区间和。毒瘤考虑了$n$个这样的修改操作,并编号为$1$~$n$。当毒瘤要出数据结构题的时候,他就将这些修改操作中选若干个出来,然后出成一道题。

    当然了,这样出的题有可能不可做。通过精妙的数学推理,毒瘤揭露了这些修改操作的关系:有$m$对“互相排斥”的修改操作,第$i$对是第$u_i$个操作和第$v_i$个操作。当一道题同时含有$u_i$和$v_i$这两个操作时,这道题就会变得不可做。另一方面,一道题中不包含任何“互相排斥”的修改操作时,这个题就是可做的。此外,毒瘤还发现了一个规律:$m-n$是一个很小的数字,且任意两个修改操作都是连通的。两个修改操作$a,b$是连通的,当且仅当存在若干操作$t_0,t_1,...,t_l$,使得$t_0=a,t_l=b$,且对$1≤i≤l$,$t_{i-1}$和$t_i$都是“互相排斥”的修改操作。

    一堆“互相排斥”的修改操作称为互斥对。现在毒瘤想知道,给定值$n$和$m$个互斥对,他共能出出多少道可做的不同的数据结构题。两道数据结构题是不同的,当且仅当有一个修改操作在其中一道题中存在,而在另一道题中不存在。

    输入输出格式

    输入格式:

    第一行为正整数$n,m$。

    接下来$m$行,每行两个正整数$u,v$,代表一对“互相排斥”的修改操作。

    输出格式:

    输出一行一个整数,代表毒瘤可以出的可做的不同的“互相排斥”的修改操作的个数。这个数可能很大,所以只输出模998244353后的值。

    输入输出样例

    输入样例#1: 复制
    3 2
    1 2
    2 3
    输出样例#1: 复制
    5
    输入样例#2: 复制
    6 8
    1 2
    1 3
    1 4
    2 4
    3 5
    4 5
    4 6
    1 6
    输出样例#2: 复制
    16
    输入样例#3: 复制
    12 18
    12 6
    3 11
    8 6
    2 9
    10 4
    1 8
    6 2
    11 5
    10 6
    12 2
    9 3
    7 6
    2 7
    3 2
    7 3
    5 6
    2 11
    12 1
    输出样例#3: 复制
    248

    说明

    样例一说明:可做的题包括空集,{1},{2},{3},{1,3}。注意,空集是合法的数据结构题

    数据范围

    $n≤10^5,n-1≤m≤n+10$。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。