51Nod－1632－B君的连通

ACM模版

描述

题解

拿到这道题，很容易发现，有效的数据只有n，其他的连通都是烟雾弹，毕竟保证是一颗树。

想到这里，知道是需要找规律推公式，可是半天没能推出公式，然后参考了一些大神的思路……

因为每炸毁一条边就多出一个连通图，所以最优是一个连通，最差是n个连通。选择一条边的概率是1/2，选择n条边就是1/2^(n-1)，那么最后题目要求乘以2^(n-1)，所以抵消了。 那么公式原型就是：

1+2∗C(n−1,1)+3∗C(n−1,2)+...+n∗C(n−1,n−1)

然后经过打表发现该序列的通式为：

ans[i]=2*ans[i-1]+2^(i-2),ans[1]=1

代码

#include <iostream> using namespace std; typedef long long ll; const int _MOD = 1e9 + 7; const int MAXN = 1e5 + 5; /* * deBug ll c[50][50]; void init() { for(int i=0; i<50; i++) c[i][0] = 1; for(int i=1; i<50; i++) { for(int j=1; j<=i; j++) { c[i][j] = c[i-1][j]+c[i-1][j-1]; } } for(int i=1; i<=20; i++) { ll sum = 0; for(int j=0; j<=i; j++) { sum += (j+1)*c[i-1][j]; } cout<<"i = "<<i<<" : "<<sum<<endl; } } */ ll ans[MAXN]; //快速求幂 ll power(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) { ans = (ans * a) % _MOD; b--; } b >>= 1; a = (a * a) % _MOD; } return ans; } void init() { ans[1] = 1; for (int i = 2; i < MAXN; i++) { ans[i] = 2 * ans[i - 1] + power(2, i - 2); ans[i] %= _MOD; } } int main(int argc, const char * argv[]) { init(); int n, x, y; while (cin >> n) { for (int i = 0; i < n - 1; i++) { cin >> x >> y; } cout << ans[n] << '\n'; } return 0; }