51Nod 1632 B君的连通(递归，快速幂)
51Nod 1632 B君的连通(递归，快速幂)
Angel_Kitty
发布于 2018-04-09 14:46:40
发布于 2018-04-09 14:46:40
基准时间限制：1 秒 空间限制：131072 KB 分值: 20
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 3Output示例
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 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-07-02 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读