#P6804. [2020福建冬令营]赢家

    ID: 6627 传统题 2000ms 128MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-补集计数子集 DP子掩码递推 (s-1)&mask位计数

[2020福建冬令营]赢家

题目描述

给定一张有 nn 个点、mm 条边的简单无向图。把每条边任选一个方向,得到一张有向图。若存在一个点 uu,使得从点 11 和点 22 出发都能到达 uu,则称这种定向合法。允许长度为零的路径。

求所有 2m2^m 种定向中合法的方案数,对 109+710^9+7 取模。

输入格式

第一行三个正整数 n,m,idn,m,id,其中 idid 为子任务编号。接下来 mm 行,每行两个整数 x,yx,y,描述一条无向边。

输出格式

输出一个整数,表示合法方案数取模后的结果。

样例

3 2 1
1 3
2 3
3

三种合法定向分别为 1→3,2→31\to3,2\to3,1→3,3→21\to3,3\to2,3→1,2→33\to1,2\to3。

4 5 1
1 3
2 3
1 4
2 4
3 4
30
5 6 1
1 3
2 3
3 4
3 5
1 4
2 5
55

数据范围

对于全部数据,2≤n≤152\le n\le15,1≤m≤n(n−1)/21\le m\le n(n-1)/2,1≤x<y≤n1\le x<y\le n。

原题分为四个子任务。第 1 组 30 分,m≤20m\le20。第 2 组 15 分,点 11 和点 22 之间恰有一条简单路径。第 3 组 20 分,n≤10n\le10。第 4 组 35 分,无额外限制。

原题 PDF