Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma GCC optimize("Ofast")
- #ifdef LOCAL
- #include "debug.h"
- #else
- #include <bits/stdc++.h>
- #define debug(x...)
- #endif
- //#define int ll
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- typedef pair <int, int> pii;
- #define sz(x) int((x).size())
- #ifdef ONLINE_JUDGE
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- #else
- mt19937 rng(1000 - 7);
- #endif
- const int N = 3e3 + 10;
- const int M = 5e2 + 10;
- //const int MOD2 = 998244353;
- const int MOD = 1e9 + 7;
- const ld eps = 1e-6;
- const pii dir[] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
- int n, a[N];
- ll dp[N][N], fact[N], C[N][N];
- signed main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- cout << fixed << setprecision(9);
- ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
- fact[0] = 1;
- for (int i = 1; i < N; i++) {
- fact[i] = (fact[i - 1] * i) % MOD;
- }
- for (int i = 0; i < N; i++) {
- C[i][0] = C[i][i] = 1;
- }
- for (int i = 1; i < N; i++) {
- for (int j = 1; j < i; j++) {
- C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
- }
- }
- cin >> n;
- for (int i = 0, x; i < n; i++) {
- cin >> x;
- a[x]++;
- }
- auto sqr = [=] (ll x) {
- return (x * x) % MOD;
- };
- dp[0][0] = 1;
- for (int i = 1; i <= n; i++) {
- for (int j = 0; j <= n; j++) {
- for (int k = 0; k <= min(a[i], j); k++) {
- dp[i][j] = (dp[i][j] +
- (dp[i - 1][j - k] * sqr(C[a[i]][k])) % MOD * fact[k]) % MOD;
- }
- }
- }
- ll ans = (dp[n][0] * fact[n]) % MOD;
- for (int i = 1; i <= n; i++) {
- if (i % 2) {
- ans = (ans - (dp[n][i] * fact[n - i]) % MOD + MOD) % MOD;
- }
- else {
- ans = (ans + (dp[n][i] * fact[n - i]) % MOD) % MOD;
- }
- }
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement