Submission #1041979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041979		hotboy2703	Ruins 3 (JOI20_ruins3)	C++17	58 / 100	1 ms	2652 KiB

ruins3

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll INF = 1e9;
const ll MAXN = 610;
ll dp[MAXN][MAXN];
ll fac[2*MAXN],fiv[2*MAXN];
const ll MOD = 1e9+7;
ll p(ll x,ll y){
    ll res = 1;
    for (;y;y>>=1,x=x*x%MOD)if (y&1)res=res*x%MOD;
    return res;
}
ll inv(ll x){
    return p(x,MOD-2);
}
ll C(ll k,ll n){
    if (k > n || k < 0)return 0;
    return fac[n] * fiv[k] % MOD * fiv[n-k] % MOD;
}
ll ways[MAXN];
bool ok[2*MAXN];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    ll n;
    cin>>n;
    for (ll i = 1;i <= n;i ++){
        ll x;cin>>x;
        ok[x] = 1;
    }
    fac[0] = 1;
    for (ll i = 1;i <= 2*n;i ++)fac[i] = fac[i-1]*i%MOD;
    fiv[2*n] = inv(fac[2*n]);
    for (ll i = 2*n-1;i >= 0;i --)fiv[i] = fiv[i+1]*(i+1)%MOD;
    for (ll i = 0;i <= n;i ++)ways[i] = (C(i,2*i) * fac[i-1])%MOD;
    // cout<<ways[1]<<' '<<ways[2]<<'\n';
    ll a,b;dp[2*n+1][0] = 1;
    a=b=0;
    for (ll i = 2 * n;i >= 1;i --){
        if (ok[i]){
            a++;
            for (ll j = b;j <= a;j ++){
                for (ll k = b;k < j;k ++){
                    dp[i][j] += dp[i+1][k] * C(j - k - 1,a - k - 1) % MOD * ways[j-k];
                    dp[i][j] %= MOD;
                }
                dp[i][j] += dp[i+1][j];
                dp[i][j] %= MOD; 
            }
            
        }
        else{
            b++;
            for (ll j = b;j <= a;j ++){
                dp[i][j] = dp[i+1][j] * (j-(b-1)) % MOD;
            }
        }
        // for (ll j = 0;j <= n;j ++)cout<<dp[i][j]<<' ';
        // cout<<'\n';
    }
    cout<<dp[1][n] * inv(p(2,n)) % MOD;
}

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