Submission #218251

#	Time	Username	Problem	Language	Result	Execution time	Memory
218251		Akashi	Ruins 3 (JOI20_ruins3)	C++14	100 / 100	481 ms	8824 KiB

ruins3

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

const int MOD = 1e9 + 7;

int n;
int a[1205];
int dp[1205][1205], C[1205][1205];
int fact[1205];

void build_pascal(){
    fact[0] = 1;
    for(int i = 1; i <= 1200 ; ++i) fact[i] = (1LL * fact[i - 1] * i) % MOD;

    C[0][0] = 1;
    for(int i = 1; i <= 1200 ; ++i){
        C[i][0] = 1;
        for(int j = 1; j <= i ; ++j){
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
            if(C[i][j] >= MOD) C[i][j] -= MOD;
        }
    }
}

inline int lgput(int x, int p){
    int ans = 1, aux = x;
    for(int i = 1; i <= p ; i = i << 1){
        if(i & p) ans = (1LL * ans * aux) % MOD;
        aux = (1LL * aux * aux) % MOD;
    }
    return ans;
}

int main()
{
//    freopen("1.in", "r", stdin);

    scanf("%d", &n);
    for(int i = 1; i <= n ; ++i)
        scanf("%d", &a[i]);

    if(a[1] == 1 || a[n] != 2 * n){
        printf("0");
        return 0;
    }

    build_pascal();

    dp[0][n + 1] = 1;
    for(int l = 1, i = 0; i < n ; ++i, l = 1 - l){
        for(int j = n + 1; j >= 1 ; --j){
            if(dp[i][j] == 0) continue ;

            int libere = a[i + 1] - (i + 1) - (n - j + 1);
            for(int k = 0; k <= min(n, min(libere, j)) ; ++k){
                if(j - k > n - i) continue ;
                int pos = 1;
                if(k == 0) pos = (n - (j - k) + 1) * 2 - (a[i + 1] - (libere - k) - 1);

                int add = 1LL * dp[i][j] * C[2 * k][k] % MOD * C[libere][k] % MOD * fact[k] % MOD;
                add = 1LL * add * pos % MOD;
                dp[i + 1][j - k] = (dp[i + 1][j - k] + add);
                if(dp[i + 1][j - k] >= MOD) dp[i + 1][j - k] -= MOD;
            }
        }
    }

    int Sol = dp[n][1];
    for(int i = 1; i <= n ; ++i) Sol = (1LL * Sol * lgput(2, MOD - 2)) % MOD;

    printf("%d", Sol);

    return 0;
}

Compilation message (stderr)

ruins3.cpp: In function 'int main()':
ruins3.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
ruins3.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~

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