徐老师的火星探索
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
徐老师所在的国家决定去火星建立观测基地！为了建立观测基地，徐老师选拔了 $n$ 个各行各业的人才，编号分辨为 $1 \sim n$但是建立观测基地对于各个领域的专业人员要求很高，有非常多的技术都需要有人懂，才能把这个任务完成
而现在徐老师统计了可能发生的事件，一共有 $m$ 件，其中包含（工程建造，水循环利用，空气循环......等等相关需求）
现在徐老师已经统计完了每个人擅长的领域，对于每个事件罗列出了两位擅长并且一定能解决该需求的人才
现在徐老师需要选一些人去建立观测基地，并且要保证他挑选的人在遇到这 $m$ 种事件一定有人擅长并且能站出来解决问题
徐老师想知道一共有哪些选人方案，但是方案数可能很大，所以徐老师会给第 $i$ 位人才设定一个系数 $a_i$，对于选拔的几位人才以后，这一组方案可以用 $a$ 的乘积来表示
例如选了 $1,2,7$ 三位人才，那么这一组方案可以用 $a_1 * a_2 * a_7$ 来表示
为了方便输出，请输出可行的方案总和并对 $mod$ 取模
输入格式
输入第一行包含三个整数 $n,m,mod$ 表示有 $n$ 个人才，$m$ 个事件输入第二行包含 $n$ 个整数，分别表示每个人才的系数 $a_i$
接下来 $m$ 行，每行包含两个整数 $x,y$ 表示第 $i$ 个事件有 $x,y$ 这两位人才可以解决
|数据点|$n,m$|
|:---:|:---:
|$1 \sim 3$|$n,m \leq 20$|
|$4 \sim 7$|$n,m \leq 28$|
|$8 \sim 10$|$n,m \leq 36$|
对于所有数据保证 $mod \leq 10^9$
输出格式
输出一个数字表示最终结果样例
3 2 10
1 1 1
1 2
2 35提示
可以选择的方案有五种 $(1,2),(1,3),(1,2,3),(2),(2,3)$ 每一种的方案值都是 $1$,总和为 $5$23CSP-S秋季提高组模拟赛(2)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-9-17 16:30
- 结束于
- 2023-9-27 16:30
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 16
