제출 #727840

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
727840		Kahou	유적 3 (JOI20_ruins3)	C++14	100 / 100	445 ms	1876 KiB

ruins3

/* In the name of God, aka Allah */
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int mod = 1e9 + 7;
int add(int a, int b) {
        a += b;
        if (a >= mod) a -= mod;
        if (a < 0) a += mod;
        return a;
}
int mul(int a, int b) {
        return 1ll*a*b%mod;
}
int pw(int a, int b) {
        int out = 1;
        while (b) {
                if (b&1) out = mul(a, out);
                a = mul(a, a);
                b >>= 1;
        }
        return out;
}

const int N = 605;
int n, a[N<<1], dp[N], f[N], C[N][N];

void solve() {
        C[0][0] = 1;
        for (int x = 1; x < N; x++) {
                C[x][0] = 1;
                for (int y = 1; y < N; y++) {
                        C[x][y] = add(C[x-1][y-1], C[x-1][y]);
                }
        }
        cin >> n;
        for (int i = 1; i <= n; i++) {
                int x;
                cin >> x;
                a[x] = 1;
        }
        f[0] = 1;
        for (int x = 1; x <= n; x++) {
                for (int i = 1; i <= x; i++) {
                        f[x] = add(f[x], mul(C[x-1][i-1], mul(mul(f[i-1], f[x-i]), x-i+2)));
                }
        }
        dp[0] = 1;
        int c0 = 0, c1 = 0;
        for (int i = 2*n; i >= 1; i--) {
                if (!a[i]) {
                        for (int x = 0; x <= n; x++) {
                                if (x <= c0) dp[x] = 0;
                                else dp[x] = mul(dp[x], x-c0);
                        }
                        c0++;
                }
                else {
                        for (int x = c1+1; x >= 1; x--) {
                                for (int y = 0; y < x; y++) {
                                        dp[x] = add(dp[x], mul(dp[y], mul(mul(C[c1-y][x-y-1], f[x-y-1]), x-y+1)));
                                }
                        }
                        c1++;
                }
        }
        cout << mul(dp[n], pw(2, mod-1-n)) << endl;
}
int main() {
        ios::sync_with_stdio(0), cin.tie(0);
        solve();
        return 0;
}

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