Submission #1363350

#TimeUsernameProblemLanguageResultExecution timeMemory
1363350yyc000123Lego Wall (EGOI22_legowall)C++20
64 / 100
512 ms12920 KiB
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int W = 250005 ;
const int H = 705 ; // 250005 ;
const int WH = 5e5+5 ;
const int P = 1e9+7 ;
int w , h ;
ll c[H][H] ;
vector<vector<ll>> dp ;

void init(){
    for(int i=0 ; i<H ; i++){
        for(int j=0 ; j<=i ; j++){
            if(!i) c[i][j] = 1 ;
            else c[i][j] = (c[i-1][j-1]+c[i-1][j])%P ;
        }
    }
}

ll qpow(int a , int idx){
    if(idx==0) return 1 ;
    else if(idx==1) return a ;
    if(idx&1) return (a*qpow(a,idx-1))%P ;
    ll temp = qpow(a,idx/2) ;
    return (temp*temp)%P ;
}

int main(){
    init() ;
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) ;
    cin >> w >> h ;
    if(w==2){
        cout << (qpow(2,h)-1+P)%P << '\n' ;
        return 0 ;
    }
    else if(h==2){
        if(w==1) cout << "1\n" ;
        else if(w==2) cout << "3\n" ;
        else cout << "2\n" ;
        return 0 ;
    }
    dp.resize(w+1,vector<ll>(h+1,0LL)) ;
    dp[0][0]=1 ;
    for(int i=1 ; i<w ; i++){
        for(int j=1 ; j<h ; j++){
            for(int l=0 ; l<=h-j ; l++) dp[i][j]+=(dp[i-1][l]*c[h-l][j])%P , dp[i][j]%=P ;
        }
    }
    ll ans = 0 ;
    for(int j=1 ; j<h ; j++) ans+=dp[w-1][j] ;
    cout << ans%P << '\n' ;
    return 0 ;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...