Advertisement
Guest User

Untitled

a guest
Oct 17th, 2017
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.70 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #pragma comment(linker, "/STACK:1000000000")
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <string>
  9. #include <cmath>
  10. #include <random>
  11.  
  12. using namespace std;
  13.  
  14. void pass(){
  15. return;
  16. }
  17.  
  18. #define int long long
  19. #define rand() (rand()<<15+rand())
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. const double EPS = 1e-6;
  23.  
  24. mt19937 rnd(rand());
  25. const int MOD = 1e9 + 7;
  26. const ll BIG_MOD = 1e18 + 7;
  27. const int MAXN = 1e6 + 7;
  28.  
  29. int form(int n){
  30. if (n < 0) return n + MOD;
  31. if (n >= MOD) return n - MOD;
  32. return n;
  33. }
  34.  
  35. int fact(int a, int b){
  36. return form((a * b) % MOD);
  37. }
  38.  
  39. int sum(int a, int b){
  40. return form(a + b);
  41. }
  42.  
  43. int power[MAXN], factorial[MAXN];
  44.  
  45. int get_pow(int a, int b){
  46. if (b == 0) return 1;
  47. if (b == 1) return a;
  48. int m = b / 2;
  49.  
  50. int p = get_pow(a, m);
  51. if (b % 2 == 0){
  52. return fact(p, p);
  53. }
  54. else{
  55. return fact(fact(p, p), a);
  56. }
  57. }
  58.  
  59. int c(int n, int k){
  60. return fact(fact(factorial[n], get_pow(factorial[k], MOD - 2)), get_pow(factorial[n - k], MOD - 2));
  61. }
  62.  
  63. signed main(){
  64. power[0] = 1;
  65. for (int i = 1; i < MAXN; ++i){
  66. power[i] = fact(power[i - 1], 2);
  67. }
  68.  
  69. factorial[0] = 1;
  70. for (int i = 1; i < MAXN; ++i){
  71. factorial[i] = fact(factorial[i - 1], i);
  72. }
  73.  
  74. cout.tie(NULL);
  75. cout.precision(20);
  76. freopen("input.txt", "r", stdin);
  77. ios_base::sync_with_stdio(false);
  78. int n;
  79. cin >> n;
  80.  
  81. int ans = 1;
  82. int s = 1;
  83. for (int i = 0; i < n; ++i){
  84. s = fact(s, 2);
  85. ans = sum(ans, s);
  86. }
  87.  
  88. for (int i = 0; i < n; ++i){
  89. int have_two_child = s - fact(c(n + i, i), 2);
  90. s = sum(s, have_two_child);
  91. ans = sum(ans, s);
  92. }
  93.  
  94. cout << ans;
  95. return 0;
  96. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement