This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |