fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define F first
  5. #define S second
  6. #define pii pair<int, int>
  7. #define eb emplace_back
  8. #define all(v) v.begin(), v.end()
  9. #define rep(i, n) for (int i = 0; i < (n); ++i)
  10. #define rep3(i, l, n) for (int i = l; i < (n); ++i)
  11. #define sz(v) (int)v.size()
  12. const int inf = 1e9 + 7;
  13. const ll INF = 1e18;
  14. #define abs(x) (x >= 0 ? x : -(x))
  15. #define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
  16. #define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
  17. template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
  18. template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
  19. template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
  20. template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
  21. template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
  22. const int mod = 1000000007;
  23. ll modpow(ll a, int b) { return b ? modpow(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }
  24. template<class T> ostream& operator<<(ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }
  25. template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
  26. template<class T, class T2> inline void add(T &a, T2 b) { a += b; if (a >= mod) a -= mod; }
  27.  
  28.  
  29.  
  30. void solve();
  31.  
  32. int main() {
  33.     ios::sync_with_stdio(false);
  34.     cin.tie(0);
  35.     cout.tie(0);
  36.  
  37.     int T;
  38.     // cin >> T;
  39.     T = 1;
  40.  
  41.     while (T--) {
  42.         solve();
  43.     }
  44. }
  45.  
  46. int n;
  47. vector<vector<int> > g;
  48. ll ans;
  49.  
  50. int dfs(int now, int prev) {
  51.     int sum = 1;
  52.     ll tmpans = 1; // すべて白
  53.     for (int nxt : g[now]) {
  54.         if (nxt == prev) continue;
  55.         int tmp = dfs(nxt, now);
  56.         sum += tmp;
  57.         add(tmpans, (modpow(2, tmp) - 1 + mod) % mod); // debuged % > +, -
  58.     }
  59.     add(tmpans, (modpow(2, n - sum) - 1 + mod) % mod);
  60.     tmpans = (modpow(2, n - 1) - tmpans + mod) % mod; // 余事象だから
  61.  
  62.     if (sz(g[now]) != 1) add(ans, tmpans); // 葉だったら部分木 1 つ
  63.     return sum;
  64. }
  65.  
  66. void solve() {
  67.     n = 200000;
  68.     // cin >> n;
  69.     g.resize(n);
  70.     rep(i, n - 1) {
  71.         int a, b;
  72.         a = i; b = i + 1;
  73.         // cin >> a >> b;
  74.         // a--; b--;
  75.         g[a].eb(b);
  76.         g[b].eb(a);
  77.     }
  78.  
  79.     /*
  80.      各頂点が何回白として含まれるか
  81.      2 つ以上の部分木で 1 つ以上黒の頂点がある
  82.      余事象 : すべて白 or 1 つの部分木だけ黒を含む
  83.      すべて白 : 1 通り
  84.      1 つの... : 2^{部分木のサイズ} - 1
  85.      - 1 : 全部白は避ける, 他の部分木の頂点はすべて白
  86.      */
  87.  
  88.     dfs(0, -1);
  89.     (ans *= modpow(modpow(2, n), mod - 2) % mod) %= mod; // 期待値
  90.     cout << ans << endl;
  91. }
  92.  
  93.  
Success #stdin #stdout 0.09s 29816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
971350365
https://ideone.com/KVU77n
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!