Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment (linker, "/STACK:256000000")
- #define _USE_MATH_DEFINES
- #define _CRT_SECURE_NO_DEPRECATE
- #define _CRT_NONSTDC_NO_DEPRECATE
- #define _CRT_SECURE_NO_WARNINGS
- #include <stdio.h>
- #include <iostream>
- #include <iomanip>
- #include <fstream>
- #include <cstdlib>
- #include <string>
- #include <cstring>
- #include <vector>
- #include <utility>
- #include <algorithm>
- #include <functional>
- #include <set>
- #include <unordered_set>
- #include <map>
- #include <unordered_map>
- #include <cmath>
- #include <queue>
- #include <memory.h>
- #include <sstream>
- #include <cassert>
- #include <ctime>
- #include <complex>
- #include <random>
- #include <bitset>
- using namespace std;
- typedef unsigned int uint32;
- typedef long long int64;
- typedef unsigned long long uint64;
- typedef long double ldouble;
- typedef pair<int, int> pii;
- typedef pair<int, int64> pil;
- typedef pair<int64, int64> pll;
- typedef pair<uint64, uint64> puu;
- typedef pair<pii, pii> piiii;
- #define pb push_back
- #define sq(x) ((x)*(x))
- #define tmin(x,y,z) (min(min((x),(y)),(z)))
- #define rand32() (((unsigned int)(rand()) << 16) | (unsigned int)(rand()))
- #define rand64() (((unsigned int64)(rand32()) << 16) | (unsigned int64)(rand32()))
- #define bit(mask, b) ((mask >> b) & 1)
- #define biton(mask, bit) (mask | (((uint32)(1)) << bit))
- #define bitoff(mask, bit) (mask & (~(((uint32)(1)) << bit)))
- #define bitputon(mask, bit) (mask |= (((uint32)(1)) << bit))
- #define bitputoff(mask, bit) (mask &= (~(((uint32)(1)) << bit)))
- #define FAIL() (*((int*)(0)))++
- #define INF ((int)(1e9) + 1337)
- #define LINF ((int64)(1e18))
- #define EPS 1e-11
- #define PI (3.1415926535897932384626433832795)
- #define y1 yy1
- #define y0 yy0
- #define j0 jj0
- //#define MOD 1000000007LL
- #define HMOD 1234567913LL
- #define HMOD2 1000000007LL
- #define HBASE 1000003
- #define REV2 500000004
- //#ifdef _MY_DEBUG
- // #define HMOD 1000000007
- // #define HBASE (1000003LL)
- //#else
- // #define HMOD ((int64)(1e18) + 3LL)
- // #define HBASE (1000037LL)
- //#endif
- #define MAX 2000000000
- mt19937 ggen;
- inline int64 comb(int64 n, int k)
- {
- int64 res = 1;
- for (int i = 0; i < k; i++)
- {
- res *= n;
- n--;
- }
- for (int i = 0; i < k; i++)
- {
- res /= i + 1;
- }
- return res;
- }
- int n;
- int64 f[51][5][51];
- int64 dyn(int sz, int pw, int ms)
- {
- if (pw == 0)
- return sz == 1;
- if (sz == 1)
- return 1;
- if (ms == 0)
- return 0;
- if (f[sz][pw][ms] != -1)
- return f[sz][pw][ms];
- int64 res = dyn(sz, pw, ms - 1);
- int64 tt = dyn(ms, 3, ms - 1);
- for (int i = 1; i <= pw && sz > i * ms && tt; i++)
- {
- int64 tres = dyn(sz - i * ms, pw - i, ms - 1);
- res += tres * comb(tt + i - 1, i);
- }
- return f[sz][pw][ms] = res;
- }
- void solve()
- {
- cin >> n;
- if (n <= 3)
- {
- cout << 1;
- return;
- }
- memset(f, -1, sizeof f);
- int64 res = dyn(n, 4, (n - 1) / 2);
- if ((n & 1) == 0)
- {
- res += comb(dyn(n / 2, 3, n / 2 - 1) + 1, 2);
- }
- cout << res;
- }
- #define TASK "chemistry"
- int main()
- {
- //testgen(50000, 100000, 50);// return 0;
- ios_base::sync_with_stdio(false); cin.tie(0);
- #ifdef _MY_DEBUG
- freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout);
- #else
- freopen(TASK ".in", "rt", stdin); freopen(TASK ".out", "wt", stdout);
- #endif
- //stresstest(8); return 0;
- ggen = mt19937(13);
- //int start = clock();
- solve();
- //cerr << (double)(clock() - start) / CLOCKS_PER_SEC << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement