Submission #895487

#	Time	Username	Problem	Language	Result	Execution time	Memory
895487		box	Ruins 3 (JOI20_ruins3)	C++17	100 / 100	158 ms	3416 KiB

ruins3

#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

const int MAXN = 606;
const int MOD = 1e9 + 7;

int N;
bool use[MAXN * 2];
int take[MAXN][MAXN];
int nck[MAXN][MAXN];
int dp[MAXN + 1], ndp[MAXN + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        use[x] = 1;
    }
    take[0][0] = 1;
    for (int n = 1; n <= N; n++) for (int k = 0; k <= n; k++) {
        i64 x = take[n - 1][k];
        if (k >= 1) x += (i64) take[n - 1][k - 1] * 2 * k;
        if (k >= 2) x += (i64) take[n - 1][k - 2] * k * (k - 1);
        take[n][k] = x % MOD;
    }
    for (int n = 0; n <= N; n++) {
        nck[n][0] = 1;
        for (int k = 1; k <= n; k++) {
            nck[n][k] = nck[n - 1][k] + nck[n - 1][k - 1];
            if (nck[n][k] >= MOD) nck[n][k] -= MOD;
        }
    }
    int cnt_rem = 0, cnt_use = 0;
    dp[0] = 1;
    for (int i = N * 2; i >= 1; i--) {
        fill(ndp, ndp + N + 1, 0);
        if (!use[i]) {
            for (int j = cnt_rem; j <= cnt_use; j++) if (dp[j])
                ndp[j] = (i64) dp[j] * (j - cnt_rem) % MOD;
            cnt_rem++;
        } else {
            for (int j = cnt_rem; j <= cnt_use; j++) if (dp[j]) {
                ndp[j] = (ndp[j] + dp[j]) % MOD;
                for (int k = 1; j + k <= cnt_use + 1; k++)
                    ndp[j + k] = (ndp[j + k] + (i64) dp[j] * (k + 1) % MOD * nck[cnt_use - j][k - 1] % MOD * take[k - 1][k - 1]) % MOD;
            }
            cnt_use++;
        }
        swap(dp, ndp);
    }
    i64 ans = dp[N];
    for (int i = 0; i < N; i++) ans = ans * (MOD + 1) / 2 % MOD;
    cout << ans << '\n';
}

• Subtask 1: 6 / 6
• Subtask 2: 52 / 52
• Subtask 3: 42 / 42