Submission #906690

#	Time	Username	Problem	Language	Result	Execution time	Memory
906690		manizare	Ruins 3 (JOI20_ruins3)	C++14	100 / 100	969 ms	11604 KiB

ruins3

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops") 
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 700 , maxw= 1e3 + 10,  lg = 18 , inf = 1e18 , mod= 1e9 + 7 ;
int dp2[maxn][maxn] , dp[maxn][maxn] , f[maxn] , inv[maxn] , pr[maxn] , a[maxn] , sm[maxn][maxn] ;

int po(int a, int b){
    if(b==0)return 1;
    int v =po(a,b/2) ;
    v = v*v%mod ;
    if(b&1) v =v*a %mod ;
    return v; 
}
int c(int n , int k){
    if(n < k || k < 0)return 0 ;
    return f[n] * inv[k]%mod * inv[n-k]%mod ; 
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    f[0] = 1;
    rep(i , 1, maxn-1){
        f[i] = f[i-1] * i % mod  ;
    }
    inv[maxn-1] = po(f[maxn-1] , mod-2); 
    per(i , maxn-2 , 0){
        inv[i] = inv[i+1] * (i+1) % mod ;
    }
    int n;cin >> n ;
    rep(i , 1, n){
        cin >> a[i] ; 
    }
    pr[0] = a[1] -1 ;
    rep(i , 1, n){
        pr[i] = pr[i-1] + (a[i+1] - a[i] - 1) ;
    }
    int a2 = po(2, mod-2); 
    dp2[1][0] = 1; dp2[1][1] = a2 ;
    rep(i , 1 , n){
        rep(j , 1, n){
            dp2[i+1][j+1] = (dp2[i+1][j+1] + a2*dp2[i][j] %mod)%mod ;
            dp2[i+1][j-1] = (dp2[i+1][j-1] + a2*dp2[i][j]%mod)%mod ;
            dp2[i+1][j] = (dp2[i+1][j] + dp2[i][j]%mod)%mod ;
        }
    }
    dp[0][0]= 1;
    rep(i , 0, n){
        rep(j , 1, i+2){
            sm[i][j] = (sm[i][j] + sm[i][j-1])%mod ;
        }
        rep(j , 0 , i){
            dp[i][j] = (dp[i][j] + sm[i][j] * inv[i-j]%mod)%mod ;
            rep(k ,  1 , n-i){
                int x = dp[i][j] * c(pr[j]-(i) , k) %mod * f[k] % mod * dp2[k][0] %mod ;                   
                dp[i+k][j] = (dp[i+k][j] + x) %mod ; 
                x = x * k%mod * f[i+k-1-j]%mod ;
                sm[i+k][j] = (sm[i+k][j] + x)%mod ; 
                dp[i+k][j] = (dp[i+k][j]-x*inv[i+k-j]%mod+mod)%mod ;
            }
        }
    }
    cout << dp[n][n]%mod << "\n";
}
/*

*/

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