51Nod 1632 B君的连通(递归,快速幂)

1632 B君的连通

基准时间限制:1 秒 空间限制:131072 KB 分值: 20

难度:3级算法题

B国拥有n个城市,其交通系统呈树状结构,即任意两个城市存在且仅存在一条交通线将其连接。A国是B国的敌国企图秘密发射导弹打击B国的交通线,现假设每条交通线都有50%的概率被炸毁,B国希望知道在被炸毁之后,剩下联通块的个数的期望是多少?

Input

一个数n(2<=n<=100000)
接下来n-1行,每行两个数x,y表示一条交通线。(1<=x,y<=n)
数据保证其交通系统构成一棵树。

Output

一行一个数,表示答案乘2^(n-1)后对1,000,000,007取模后的值。

Input示例

3
1 2
1 3

Output示例

8

题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1632

分析:

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll mod=1000000007;
 5 inline ll read()
 6 {
 7     ll x=0,f=1;
 8     char ch=getchar();
 9     while(ch<'0'||ch>'9')
10     {
11         if(ch=='-')
12             f=-1;
13         ch=getchar();
14     }
15     while(ch>='0'&&ch<='9')
16     {
17         x=x*10+ch-'0';
18         ch=getchar();
19     }
20     return x*f;
21 }
22 ll n,x,y;
23 ll a[100010]={0,1};
24 ll qpow(ll x,ll p)
25 {
26     ll ret=1;
27     for(;p;p>>=1,x=x*x%mod)
28     {
29         if(p&1)
30             ret=ret*x%mod;
31     }
32     return ret;
33 }
34 int main()
35 {
36     n=read();
37     ll ans=0;
38     for(int i=1;i<n;i++)
39     {
40         x=read();
41         y=read();
42     }
43     for(ll i=2;i<=100001;i++)
44         a[i]=2*a[i-1]+qpow(2,i-2),a[i]%=mod;
45     cout<<a[n]<<endl;
46     return 0;
47 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据处理

碰运气的约会-几何概率

25750
来自专栏机器之心

CVPR 2017李沐介绍MXNet新接口Gluon:高效支持命令式与符号式编程

选自Github 机器之心编译 参与:Smith、蒋思源 MXNet 现已广泛应用于生产环境中,并且因为其运行速度而饱受赞誉。现在,MXNet 有了十分重要的新...

34750
来自专栏企鹅号快讯

外国网友如何使用机器学习将邮件分类?其实很简单

AiTechYun 编辑:Yining 背景:一名叫做Anthony Dm.的外国网友试图利用机器学习将一堆未标记的电子邮件进行分类,以下是他对这次操作发表的文...

23680
来自专栏媒矿工厂

超高清内容生产中的视频编码技术

通过逐步引入宽色域(WCG)、高动态范围(HDR)、更高的分辨率和更高的帧率(HFR)等用以改善视频消费者观看体验的新特性,Ultra-HD(UHD-1)预计将...

57240
来自专栏算法+

简洁明了的插值音频重采样算法例子 (附完整C代码)

近一段时间在图像算法以及音频算法之间来回游走。 经常有一些需求,需要将音频进行采样转码处理。 现有的知名开源库,诸如: webrtc , sox等, 代码阅读起...

1.6K80
来自专栏IT派

如何用 OpenCV、Python 和深度学习实现面部识别?

这篇文章首先将简单介绍下基于深度学习的面部识别的工作原理,以及“深度度量学习”(deep metric learning)的概念。接下来我会帮你安装好面部识别需...

16940
来自专栏华章科技

教你用300万共享单车出行数据,预测骑行目的地 !(附源码)

标注数据中包含300万条出行记录数据,覆盖超过30万用户和40万摩拜单车。数据包括骑行起始时间和地点、车辆ID、车辆类型和用户ID等信息。参赛选手需要预测骑行目...

16620
来自专栏鸿的学习笔记

用python讲故事(中)

5. Assemble a corpus of data to validate subjective(human) interpretation

9830
来自专栏AI科技评论

干货 | 如何配置一台适用于深度学习的工作站?

本文来源于王璋在知乎问题【如何配置一台适用于深度学习的工作站?】下的回答,AI科技评论获其授权转载。 问题详情 如何配置一台适用于深度学习的工作站? 刚买两块T...

597140
来自专栏量子位

众筹项目能否成功?用机器学习预测可以早知道

安妮 编译自 Shrikar Archak 量子位出品 | 公众号 QbitAI Kickstarter是一家美国的众筹平台。自2009年成立至今,已经有36万...

39150

扫码关注云+社区

领取腾讯云代金券