Advertisement
ivnikkk

Untitled

Dec 29th, 2021
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.95 KB | None | 0 0
  1. #include<iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <iomanip>
  6. #include <fstream>
  7. #include <string>
  8. #include <set>
  9. #include <deque>
  10. #include <queue>
  11. #include <map>
  12. #include <bitset>
  13. #include <random>
  14. #include <cassert>
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. using namespace std;
  18. typedef long long            ll;
  19. typedef unsigned long long   ull;
  20. typedef long double          ld;
  21. #define sqrt              sqrtl
  22. #define endl              "\n"
  23. #define all(a)            a.begin(), a.end()
  24. #define pb                push_back
  25. #define F               first
  26. #define S                second
  27.  
  28. const ll inf = 1e18;
  29. long double eps = 1e-18;
  30. ll mod = 1e9 + 7;
  31.  
  32. template<typename T>
  33. T add(T x) {
  34.     return x;
  35. }
  36.  
  37. template<typename T, typename... Ts>
  38. T add(T x, Ts... y) {
  39.     T res = x + add(y...);
  40.     if (res >= mod)
  41.         res -= mod;
  42.     return res;
  43. }
  44.  
  45. template<typename T, typename... Ts>
  46. T sub(T x, Ts... y) {
  47.     return add(x, mod - add(y...));
  48. }
  49.  
  50. template<typename T, typename... Ts>
  51. void udd(T& x, Ts... y) {
  52.     x = add(x, y...);
  53. }
  54.  
  55. template<typename T>
  56. T mul(T x) {
  57.     return x;
  58. }
  59.  
  60. template<typename T, typename... Ts>
  61. T mul(T x, Ts... y) {
  62.     return (x * 1ll * mul(y...)) % mod;
  63. }
  64.  
  65. template<typename T, typename... Ts>
  66. void uul(T& x, Ts... y) {
  67.     x = mul(x, y...);
  68. }
  69. // segment_tree
  70. const ll N = 100000;
  71. ll  tree[N * 4], a[N];
  72. void build(ll v, ll l, ll r) {
  73.     if (l == r) {
  74.         tree[v] = a[l];
  75.         return;
  76.     }
  77.     else {
  78.         ll m = (r + l) / 2;
  79.         build(v * 2 + 1, l, m);
  80.         build(v * 2 + 2, m + 1, r);
  81.         tree[v] = tree[2 * v] + tree[2 * v + 1];
  82.     }
  83. }
  84. void update(ll v, ll tl, ll tr, ll pos, ll new_val) {
  85.     if (tl == tr)
  86.         tree[v] = new_val;
  87.     else {
  88.         ll tm = (tl + tr) / 2;
  89.         if (pos <= tm)
  90.             update(v * 2, tl, tm, pos, new_val);
  91.         else
  92.             update(v * 2 + 1, tm + 1, tr, pos, new_val);
  93.         tree[v] = tree[v * 2] + tree[v * 2 + 1];
  94.     }
  95. }
  96. ll sum(ll v, ll tl, ll tr, ll l, ll r) {
  97.     if (l > r)
  98.         return 0;
  99.     if (l == tl && r == tr)
  100.         return tree[v];
  101.     ll tm = (tl + tr) / 2;
  102.     return sum(v * 2, tl, tm, l, min(r, tm)) + sum(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
  103. }
  104. //const int Lg = 63;
  105. //int cnt[2][Lg], a[N];
  106. //ll ans = 0;
  107. //
  108. //struct trie {
  109. //    struct node {
  110. //        int go[2] = { -1, -1 }, count = 0;
  111. //        ll sum = 0;
  112. //    };
  113. //    vector<node> t = { {} };
  114. //    void add(ll x) {
  115. //        int v = 0;
  116. //        for (int i = Lg - 1; i > -1; --i) {
  117. //            t[v].count++;
  118. //            int b = (int)((x >> i) & 1LL);
  119. //            if (t[v].go[b] == -1) {
  120. //                t[v].go[b] = (int)size(t);
  121. //                t.emplace_back();
  122. //            }
  123. //            int to = t[v].go[b ^ 1];
  124. //            if (to != -1) {
  125. //                ans += cnt[b ^ 1][i] * 1LL * t[to].count + t[to].sum;
  126. //            }
  127. //            to = t[v].go[b];
  128. //            t[to].sum -= cnt[b][i];
  129. //            v = to;
  130. //        }
  131. //        ++t[v].count;
  132. //    }
  133. //};
  134. void solve() {
  135.     //dp[i][j] i - число кубиков j число кубиков в основании
  136.     ll n;
  137.     cin >> n;
  138.     vector<vector<ll>>dp(n + 1, vector<ll>(n + 1, 0));
  139.     dp[0][0] = 1;
  140.     for (ll i = 1; i <= n; i++) {
  141.         for (ll f = 0; f <= i; f++)
  142.             for (ll j = 0; j < f; j++) {
  143.                 dp[i][f] += dp[i - f][j];
  144.             }
  145.     }
  146.     ll sum = 0;
  147.     for (ll i = 0; i <= n; i++)sum += dp[n][i];
  148.     cout << sum;
  149. }
  150. signed main() {
  151.     ios_base::sync_with_stdio(false);
  152.     cin.tie(nullptr);
  153.     ll t = 1;
  154.     //cin >> t;
  155.     while (t--) {
  156.        solve();
  157.     }
  158.     /*int n;
  159.     cin >> n;
  160.     trie bor;
  161.     for (int i = 0; i < n; ++i) {
  162.         ll x;
  163.         cin >> x;
  164.         for (int j = Lg - 1; j > -1; --j) {
  165.             cnt[(x >> j) & 1][j]++;
  166.         }
  167.         bor.add(x);
  168.     }
  169.     cout << ans;*/
  170.  
  171. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement