101 Hack 44 - Expected Tree Leaves

Anna loves studying trees (i.e., undirected acyclic connected graphs). She even invented the following algorithm to randomly generate a tree with  vertices:

1. Initially, we have a positive integer, , and a tree with one vertex (numbered ).
2. Next, we add vertices  one at a time. To add each vertex  (where ), we create edge where  is randomly chosen from the previously-added vertices (i.e., vertices in the inclusive range from  to ).

We define a leaf to be a vertex whose degree (i.e., number of connected edges) is exactly . Note that vertex  is considered to be the root, so it's never counted as a leaf.

Given the number of vertices in the tree, help Anna by finding the expected number, , of leaves in the tree. Then print the value of  as your answer.

Input Format

A single integer, , denoting the number of vertices in the tree.

Constraints

Output Format

Print the value of , where  is the expected number leaves in the generated tree.

Sample Input 0

3

Sample Output 0

9

Explanation 0

Given , we can generate two possible trees with Anna's algorithm:

The first tree only has one leaf (), and the second one has two leaves ( and ). This gives us an expected value of , so we print the value of  as our answer.

Note: Recall that vertex  is the root and never counts as a leaf.

Solution:

1. #include <bits/stdc++.h>
2. #define pb push_back
3. using namespace std;
4. typedef long long LL;
5. const int S = 100003;
6. const int MOD = 1e9+7;
7. const double pi = 2 * acos( 0.0 );
8.  
9. inline int _Int(){ int x; scanf( "%d", &x ); return x; }
10. inline LL _LLi(){ LL x; scanf( "%lld", &x ); return x; }
11. void pruts(){ puts( "-1" ); exit( EXIT_SUCCESS ); }
12.  
13. int dirX[] = { 1, 0, -1, 0, 1, -1, 1, -1 };
14. int dirY[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
15. int rX[] = { 1, 1, 2, 2, -1, -1, -2, -2 };
16. int rY[] = { 2, -2, 1, -1, 2, -2, 1, -1 };
17.  
18. template < class T > T tri_Area( T x1, T y1, T x2, T y2, T x3, T y3 ){ return abs( x1*( y2-y3 ) - y1*( x2-x3 ) + ( x2*y3-x3*y2 ) );};
19. template < class T > T Distance( T x1, T y1, T x2, T y2 ){ return sqrt( ( x1-x2 ) * ( x1-x2 ) + ( y1-y2 ) * ( y1-y2 ) ); };
20. template < class T > T bigMod( T n, T p, T m ){ if( p == 0 )return 1; if( p&1 )return ( n*bigMod( n, p-1, m ) )%m; T x = bigMod( n, p/2, m ); return ( x*x )%m; };
21.  
22. int sset(int N, int pos){return N=N|(1<<pos);}
23. bool check(int N, int pos){return (bool)(N&(1<<pos));}
24. int reset(int N, int pos){return N=N&~(1<<pos);}
25. /*******************###########################################********************
26. ********************##   MD. YA-SEEN ARAFAT(ThunderStroke)   ##********************
27. ********************##    CSE, University of Asia Pacific    ##********************
28. ********************###########################################********************/
29.  
30. void Love(){
31.     LL g = _LLi();
32.     LL n = g;
33.     n--;
34.     LL sum = ( n+1 );
35.     for( int i = 1; i <= g; i++ ){
36.         sum *= i;
37.         sum %= MOD;
38.     }
39.     LL ans = ( sum%MOD * bigMod( 2LL, (LL)MOD-2LL, (LL)MOD )%MOD )%MOD;
40.     cout << ans << endl;
41. }
42.  
43. int main(){
44.     #ifndef ONLINE_JUDGE
45. //        freopen("in.txt", "r", stdin);
46. //        freopen("n.txt", "w", stdout);
47.     #endif
48.     Love();
49.     return 0;
50. }