제출 #1116924

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1116924		byebye75	유적 3 (JOI20_ruins3)	C++14	100 / 100	314 ms	8948 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;
}

컴파일 시 표준 에러 (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]
   38 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
ruins3.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~

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