Submission #1307510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307510		Sharky	Ruins 3 (JOI20_ruins3)	C++20	6 / 100	2 ms	840 KiB

ruins3

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

#define int long long
const int mod = 1e9 + 7;
const int N = 608;

int bm(int b, int p) {
    if (!p) return 1;
    int res = bm(b, p / 2);
    res = res * res % mod;
    if (p % 2 == 1) res = res * b % mod;
    return res;
}

int n, f[N << 1][N], fac[N], ifac[N], a[N << 1], sf[N << 1], g[N], fib[N][N];

int ncr(int x, int y) {
    if (x < y || x < 0 || y < 0) return 0;
    return fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    fac[0] = ifac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i - 1] * i % mod;
        ifac[i] = bm(fac[i], mod - 2);
    }
    for (int i = 1; i <= n; i++) {
        int val;
        cin >> val;
        a[val] = 1;
    }
    for (int i = 2 * n; i >= 1; i--) sf[i] = sf[i + 1] + a[i];

    int inv = bm(2, mod - 2);
    g[0] = 1;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) g[i] += g[j - 1] * g[i - j] % mod * ncr(i - 1, j - 1) % mod * (i - j + 2) % mod;

    if (!a[2 * n]) return cout << "0\n", 0;
    f[2 * n + 1][0] = 1;
    for (int i = 2 * n; i >= 1; i--) {
        for (int j = 0; j <= n; j++) {
            if (a[i]) {
                f[i][j] = f[i + 1][j];
                for (int k = 0; k < j; k++) (f[i][j] += f[i + 1][k] * g[j - k - 1] % mod * (j - k + 1) % mod * ncr(sf[i + 1] - k, j - k - 1) % mod) %= mod;
            } else {
                int num_dead = (2 * n - i) - sf[i + 1];
                // cout << num_dead << '\n';
                if (j > num_dead) f[i][j] = f[i + 1][j] * ((j - num_dead + mod) % mod) % mod;
            }
            // cout << "dp @ " << i << " " << j << " = " << f[i][j] << "\n";
        }
    }
    cout << f[1][n] * bm(inv, n) % mod << '\n';
}

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