#P6916. duliu

    ID: 6747 传统题 4000ms 888MiB 尝试: 8 已通过: 1 难度: 10 上传者: 标签>难度分类NOI/NOI+/CTS组合数学字典序排名与反排名图论独立集仙人掌图动态规划计数 DP动态 DP树链剖分维护 DP转移矩阵乘积数据结构静态带权平衡树CF3200

duliu

Problem C. 点独立集(duliu)

时间限制:3s;空间限制:1024MB。

题目描述

给定一张连通无向图,满足每条边最多在一个点简单环上。再给出它的一个点独立集,求字典序小于该点独立集的非空点独立集数量。

点独立集指任意两点间都没有边相连的点集。将集合 S,TS,T 分别按升序排成序列 s,ts,t,设最长公共前缀的长度为 ll。当且仅当以下任一条件成立,称 SS 的字典序小于 TT:

  • l=∣s∣l=|s| 且 l<∣t∣l<|t|;
  • l<∣s∣l<|s| 且 l<∣t∣l<|t|,并且 sl+1<tl+1s_{l+1}<t_{l+1}。

答案对 998244353998244353 取模后输出。保证没有自环,但可能有重边。

输入格式

从标准输入读入。第一行三个正整数 n,m,zn,m,z,分别为图的点数、边数、给定独立集的大小。

接下来 mm 行,每行两个正整数 u,vu,v,表示连接点 u,vu,v 的一条边。之后一行有 zz 个互不相同的正整数,表示给定独立集中的点。

输出格式

向标准输出写出一个整数,表示答案对 998244353998244353 取模后的值。

样例 1

4 3 2
1 2
2 3
3 4
2 4
4

四个独立集为 {1}\{1\}、{1,3}\{1,3\}、{1,4}\{1,4\}、{2}\{2\}。

样例二、三

见原题下发文件 ex_duliu2.in、ex_duliu2.out,以及 ex_duliu3.in、ex_duliu3.out。

限制与约定

记每条边所在点简单环的最大数量为 xx。所有测试点满足 1≤n≤10000001\le n\le1000000,0≤x≤10\le x\le1。

测试点编号 n=n= x=x= 特殊性质
1 5 0 无
2 10
3 15
4 20
5—7 1000
8—10 1
11—13 1000000 0 第 ii 条边连接点 ii 和点 i+1i+1
14—15 100000 无
16 300000
17 1000000
18—20 100000 1
21—22 300000
23 500000
24—25 1000000