Submission #210032

#TimeUsernameProblemLanguageResultExecution timeMemory
210032apostoldaniel854Zapina (COCI20_zapina)C++14
110 / 110
108 ms1272 KiB
/* https://oj.uz/problem/view/COCI20_zapina */ #include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define dbg(x) cerr << #x << " " << x << "\n" const int N = 350; /// dp[i][many] = the number of ways to not make anybody happy with many tasks and on prefix 1..i of programmers const int MOD = 1e9 + 7; int dp[1 + N][1 + N]; int comb[1 + N][1 + N]; void add (int &a, int b) { a += b; if (a >= MOD) a -= MOD; } int main() { ios::sync_with_stdio (false); cin.tie (0); cout.tie (0); int n; cin >> n; for (int i = 0; i <= n; i++) { comb[i][0] = 1; for (int j = 1; j <= i; j++) comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD; } dp[0][0] = 1; for (int i = 1; i <= n; i++) { for (int many = 0; many <= n; many++) { for (int j = 0; j <= many; j++) { if (j == i) continue; add (dp[i][many], 1ll * dp[i - 1][many - j] * comb[n - (many - j)][j] % MOD); } } } int ans = 1; for (int i = 1; i <= n; i++) ans = 1ll * ans * n % MOD; ans -= dp[n][n]; if (ans < 0) ans += MOD; cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...