Submission #1138820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138820		OI_Account	Ruins 3 (JOI20_ruins3)	C++20	100 / 100	241 ms	8924 KiB

ruins3

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

typedef long long ll;

const int N = 600, K = 1200;
const ll MOD = 1'000'000'007;

int n, k, mark[K + 10], s[K + 10];
ll preDP[N + 10][N + 10], pre[N + 10];
ll dp[K + 10][N + 10];
ll fact[N + 10], invFact[N + 10];

void readInput() {
    cin >> n;
    k = n + n;
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        mark[a] = i;
    }
}

bool checkFirst() {
    return !mark[1] && mark[k];
}

ll power(ll x, ll k) {
    ll pw = x, res = 1;
    while (k) {
        if (k & 1)
            res = res * pw % MOD;
        k >>= 1;
        pw = pw * pw % MOD;
    }
    return res;
}

void calcFact() {
    fact[0] = invFact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i % MOD;
        invFact[i] = power(fact[i], MOD - 2);
    }
}

ll C(int n, int r) {
    if (n < r || r < 0 || n < 0)
        return 0;
    return (fact[n] * invFact[n - r] % MOD) * invFact[r] % MOD;
}

void calcS() {
    s[k + 1] = 0;
    for (int i = k; i >= 1; i--)
        s[i] = s[i + 1] + (mark[i] == 0);
}

void calcPreDP() {
    preDP[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        preDP[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            ll case1 = preDP[i - 1][j];
            ll case2 = 2ll * preDP[i - 1][j - 1] % MOD;
            ll case3 = (2 <= j? preDP[i - 1][j - 2]: 0);
            preDP[i][j] = (case1 + case2 + case3) % MOD;
        }
    }
}

void calcPre() {
    calcPreDP();
    for (int i = 1; i <= n; i++) 
        pre[i] = (preDP[i - 1][i - 1] * fact[i - 1] % MOD) * (ll) (i + 1) % MOD;
}

void calcDP() {
    int cnt = 0;
    dp[k + 1][0] = 1;
    for (int i = k; i >= 1; i--) {
        cnt += (mark[i] != 0);
        for (int l = 0; l <= cnt; l++) {
            if (!mark[i]) {
                int remain = 2 * l - (k - i - cnt) - l;
                dp[i][l] = (ll) max(0, remain) * dp[i + 1][l] % MOD;
                continue;
            }
            dp[i][l] = dp[i + 1][l];
            for (int j = 1; j <= l; j++) {
                ll case1 = C(cnt - (l - j) - 1  , j - 1);
                ll case2 = pre[j] * dp[i + 1][l - j] % MOD;
                ll tmp = case1 * case2 % MOD;
                dp[i][l] = (dp[i][l] + tmp) % MOD;
            }
        }
    }
}

void writeOutput() {
    ll ans = dp[1][n];
    cout << ans * power(power(2, n), MOD - 2) % MOD << flush;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcFact();
    calcS();
    calcPre();
    calcDP();
    writeOutput();
    return 0;
}

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