Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 6224 --3.建造军营
6224: 3.建造军营
警告！
题目
状态
题解
题目描述
A 国与 B 国正在激烈交战中，A 国打算在自己的国土上建造一些军营。 A 国的国土由 $n$ 座城市组成，$m$ 条双向道路连接这些城市，使得**任意两座城市均可通过道路直接或间接到达**。A 国打算选择一座或多座城市（**至少一座**），并在这些城市上各建造一座军营。 众所周知，军营之间的联络是十分重要的。然而此时 A 国接到情报，B 国将会于不久后袭击 A 国的一条道路，但具体的袭击目标却无从得知。如果 B 国袭击成功，这条道路将被切断，可能会造成 A 国某两个军营无法互相到达，这是 A 国极力避免的。因此 A 国决定派兵看守若干条道路（**可以是一条或多条，也可以一条也不看守**)，A 国有信心保证被派兵看守的道路能够抵御 B 国的袭击而不被切断。 A 国希望制定一个建造军营和看守道路的方案，使得 B 国袭击的无论是 A 国的哪条道路，都不会造成某两座军营无法互相到达。现在，请你帮 A 国计算一下可能的建造军营和看守道路的方案数共有多少。由于方案数可能会很多，你只需要输出其对 $1,000,000,007\left(10^{9}+7\right)$ 取模的值即可。两个方案被认为是不同的，当且仅当存在至少一 座城市在一个方案中建造了军营而在另一个方案中没有，或者存在至少一条道路在一个 方案中被派兵看守而在另一个方案中没有。
输入
第一行包含两个正整数 $n,m$，分别表示城市的个数和双向道路的数量。 接下来 $m$ 行，每行包含两个正整数 $u_{i},v_{i}$，描述一条连接 $u_{i}$ 和 $v_{i}$ 的双向道路。保证没有重边和自环。
输出
输出一行包含一个整数，表示建造军营和看守道路的方案数对 $1,000,000,007\left(10^{9}+ 7\right)$ 取模的结果。
样例输入输出
输入#1
复制
2 1 1 2
输出#1
复制
5
输入#2
复制
4 4 1 2 2 3 3 1 1 4
输出#2
复制
184
提示
### 样例 1 解释 A 国有两座城市，一条道路连接他们。所有可能的方案如下： - 在城市 $1$ 建军营, 不看守这条道路; - 在城市 $1$ 建军营, 看守这条道路; - 在城市 $2$ 建军营, 不看守这条道路; - 在城市 $2$ 建军营, 看守这条道路; - 在城市 $1,2$ 建军营, 看守这条道路。 ### 数据规模与约定 对所有数据，保证 $1 \leq n \leq 5 \times 10^5$，$n - 1 \leq m \leq 10^6$，$1 \leq u_i, v_i \leq n$，$u_i \neq v_i$。 各测试点的信息如下 |测试点编号 | $n \leq $ | $m \leq $| 特殊条件 | | :-: | :-: | :-: | :-: | | $1 \sim 3$ | $8$ | $10$ | 无 | | $4 \sim 7$ | $16$ | $25$ | 无 | | $8 \sim 9$ | $3000$ | $5000$ | 无 | | $10 \sim 11$ | $5 \times 10^5$ | $10^6$ | 特殊性质 $\mathrm{A}$ | | $12 \sim 14$ | $5 \times 10^5$ | $10^6$ | $m = n - 1$ | | $15 \sim 16$ | $5 \times 10^5$ | $10^6$ | $m = n$ | | $17 \sim 20$ | $5 \times 10^5$ | $10^6$ | 无 | 特殊性质 $\mathrm{A}$：保证 $m=n-1$ 且第 $i$ 条道路连接城市 $i$ 与 $i+1$。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
省选/NOI-
标签
树
点击显示
递交数
3
已通过
1
通过率
34%
时间限制
1 秒
内存限制
512 MB
来源
NOIP2022
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和