Submission #588764

#TimeUsernameProblemLanguageResultExecution timeMemory
588764nguyen31hoang08minh2003Zapina (COCI20_zapina)C++14
110 / 110
296 ms2208 KiB
/* +------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+ |../\..|../\..|../\..|../\..|../\..|../\..|../\..|../\..|../\..|../\..|../\..|../\..|../\..|../\..|../\..|../\..|../\..| |\/..\/|\/..\/|\/..\/|\/..\/|\/..\/|\/..\/|\/..\/|\/..\/|\/..\/|\/..\/|\/..\/|\/..\/|\/..\/|\/..\/|\/..\/|\/..\/|\/..\/| |/....\|/....\|/....\|/....\|/....\|/....\|/....\|/....\|/....\|/....\|/....\|/....\|/....\|/....\|/....\|/....\|/....\| +------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+ |\..../|\..../|\..../|\..../|\..../|\..../|\..../|\..../|\..../|\..../|\..../|\..../|\..../|\..../|\..../|\..../|\..../| |/\../\|/\../\|/\../\|/\../\|/\../\|/\../\|/\../\|/\../\|/\../\|/\../\|/\../\|/\../\|/\../\|/\../\|/\../\|/\../\|/\../\| |..\/..|..\/..|..\/..|..\/..|..\/..|..\/..|..\/..|..\/..|..\/..|..\/..|..\/..|..\/..|..\/..|..\/..|..\/..|..\/..|..\/..| +------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+------+ */ #include <bits/stdc++.h> #define fore(i, a, b) for (signed i = (a), i##_last = (b); i < i##_last; ++i) #define fort(i, a, b) for (signed i = (a), i##_last = (b); i <= i##_last; ++i) #define ford(i, a, b) for (signed i = (a), i##_last = (b); i >= i##_last; --i) #define fi first #define se second #define pb push_back #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() using namespace std; using ll = long long; using ld = long double; template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;}; template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;}; typedef unsigned long long ull; typedef pair<int, int> ii; typedef vector<ll> vi; typedef vector<ii> vii; typedef vector<vi> vvi; typedef vector<vii> vvii; int findPeriod(ll a, int m) { int x = 1; map<int, int> f; for (int i = 0;; ++i) { const auto g = f.find(x); if (g != f.end()) return i - (g -> se); f[x] = i; x = (x * a) % m; } } const int maxN = 355, MOD = 1e9 + 7; int n; int C(int n, int k) { static int c[maxN][maxN]; static bool seen[maxN][maxN]; if (n == k) return 1; if (n < k || n <= 0) return 0; if (!seen[n][k]) { seen[n][k] = true; c[n][k] = (C(n - 1, k) + C(n - 1, k - 1)) % MOD; } return c[n][k]; } int DP(int x, int y, bool z) { static int dp[maxN][maxN][2]; static bool seen[maxN][maxN][2]; if (x <= 0) return !y && z; if (!seen[x][y][z]) { seen[x][y][z] = true; fort(t, 0, y) if (t == x) { if (z) continue; (dp[x][y][z] += 1LL * ((DP(x - 1, y - t, false) + DP(x - 1, y - t, true)) % MOD) * C(y, t) % MOD) %= MOD; } else (dp[x][y][z] += 1LL * DP(x - 1, y - t, z) * C(y, t) % MOD) %= MOD; } return dp[x][y][z]; } int main() { int n; #ifdef LOCAL freopen("input.INP", "r", stdin); #endif // LOCAL cin.tie(0) -> sync_with_stdio(0); cout.tie(0); cin >> n; cout << DP(n, n, false) << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...