Advertisement
Guest User

Problem 100125C solution

a guest
Oct 10th, 2016
245
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.55 KB | None | 0 0
  1. #pragma comment (linker, "/STACK:256000000")
  2.  
  3. #define _USE_MATH_DEFINES
  4. #define _CRT_SECURE_NO_DEPRECATE
  5. #define _CRT_NONSTDC_NO_DEPRECATE
  6. #define _CRT_SECURE_NO_WARNINGS
  7. #include <stdio.h>
  8. #include <iostream>
  9. #include <iomanip>
  10. #include <fstream>
  11. #include <cstdlib>
  12. #include <string>
  13. #include <cstring>
  14. #include <vector>
  15. #include <utility>
  16. #include <algorithm>
  17. #include <functional>
  18. #include <set>
  19. #include <unordered_set>
  20. #include <map>
  21. #include <unordered_map>
  22. #include <cmath>
  23. #include <queue>
  24. #include <memory.h>
  25. #include <sstream>
  26. #include <cassert>
  27. #include <ctime>
  28. #include <complex>
  29. #include <random>
  30. #include <bitset>
  31.  
  32. using namespace std;
  33.  
  34. typedef unsigned int uint32;
  35. typedef long long int64;
  36. typedef unsigned long long uint64;
  37. typedef long double ldouble;
  38. typedef pair<int, int> pii;
  39. typedef pair<int, int64> pil;
  40. typedef pair<int64, int64> pll;
  41. typedef pair<uint64, uint64> puu;
  42. typedef pair<pii, pii> piiii;
  43.  
  44. #define pb push_back
  45. #define sq(x) ((x)*(x))
  46. #define tmin(x,y,z) (min(min((x),(y)),(z)))
  47. #define rand32() (((unsigned int)(rand()) << 16) | (unsigned int)(rand()))
  48. #define rand64() (((unsigned int64)(rand32()) << 16) | (unsigned int64)(rand32()))
  49. #define bit(mask, b) ((mask >> b) & 1)
  50. #define biton(mask, bit) (mask | (((uint32)(1)) << bit))
  51. #define bitoff(mask, bit) (mask & (~(((uint32)(1)) << bit)))
  52. #define bitputon(mask, bit) (mask |= (((uint32)(1)) << bit))
  53. #define bitputoff(mask, bit) (mask &= (~(((uint32)(1)) << bit)))
  54. #define FAIL() (*((int*)(0)))++
  55. #define INF ((int)(1e9) + 1337)
  56. #define LINF ((int64)(1e18))
  57. #define EPS 1e-11
  58. #define PI (3.1415926535897932384626433832795)
  59. #define y1 yy1
  60. #define y0 yy0
  61. #define j0 jj0
  62. //#define MOD 1000000007LL
  63. #define HMOD 1234567913LL
  64. #define HMOD2 1000000007LL
  65. #define HBASE 1000003
  66. #define REV2 500000004
  67.  
  68.  
  69. //#ifdef _MY_DEBUG
  70. //    #define HMOD 1000000007
  71. //    #define HBASE (1000003LL)
  72. //#else
  73. //    #define HMOD ((int64)(1e18) + 3LL)
  74. //    #define HBASE (1000037LL)
  75. //#endif
  76. #define MAX 2000000000
  77. mt19937 ggen;
  78.  
  79. inline int64 comb(int64 n, int k)
  80. {
  81.     int64 res = 1;
  82.     for (int i = 0; i < k; i++)
  83.     {
  84.         res *= n;
  85.         n--;
  86.     }
  87.     for (int i = 0; i < k; i++)
  88.     {
  89.         res /= i + 1;
  90.     }
  91.     return res;
  92. }
  93.  
  94. int n;
  95. int64 f[51][5][51];
  96.  
  97. int64 dyn(int sz, int pw, int ms)
  98. {
  99.     if (pw == 0)
  100.         return sz == 1;
  101.     if (sz == 1)
  102.         return 1;
  103.     if (ms == 0)
  104.         return 0;
  105.     if (f[sz][pw][ms] != -1)
  106.         return f[sz][pw][ms];
  107.    
  108.     int64 res = dyn(sz, pw, ms - 1);
  109.     int64 tt = dyn(ms, 3, ms - 1);
  110.     for (int i = 1; i <= pw && sz > i * ms && tt; i++)
  111.     {
  112.         int64 tres = dyn(sz - i * ms, pw - i, ms - 1);
  113.         res += tres * comb(tt + i - 1, i);
  114.     }
  115.  
  116.     return f[sz][pw][ms] = res;
  117. }
  118.  
  119. void solve()
  120. {
  121.     cin >> n;
  122.     if (n <= 3)
  123.     {
  124.         cout << 1;
  125.         return;
  126.     }
  127.     memset(f, -1, sizeof f);
  128.     int64 res = dyn(n, 4, (n - 1) / 2);
  129.     if ((n & 1) == 0)
  130.     {
  131.         res += comb(dyn(n / 2, 3, n / 2 - 1) + 1, 2);
  132.     }
  133.     cout << res;
  134. }
  135.  
  136. #define TASK "chemistry"
  137. int main()
  138. {
  139.     //testgen(50000, 100000, 50);// return 0;
  140.     ios_base::sync_with_stdio(false); cin.tie(0);
  141. #ifdef _MY_DEBUG
  142.     freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout);
  143. #else
  144.     freopen(TASK ".in", "rt", stdin); freopen(TASK ".out", "wt", stdout);
  145. #endif
  146.     //stresstest(8); return 0;
  147.     ggen = mt19937(13);
  148.  
  149.     //int start = clock();
  150.     solve();
  151.     //cerr << (double)(clock() - start) / CLOCKS_PER_SEC << '\n';
  152.  
  153.     return 0;
  154. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement