제출 #1364227

#제출 시각아이디문제언어결과실행 시간메모리
1364227yyc000123Lego Wall (EGOI22_legowall)C++20
64 / 100
524 ms12868 KiB
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int W = 250005 ;
const int H = 250005 ;
const int WH = 5e5+5 ;
const int P = 1e9+7 ;
int w , h ;
ll c[705][705] ;
vector<vector<ll>> dp ;

void init(){
    for(int i=0 ; i<705 ; 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(){
    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 ;
    }
    // this is the solution for time complexity of O(WH^2)
    // we need to construct another solution which time complexity is about O(W^2)
    // then when WH^2<=W^2 we solve it by using the first solution , else use the second one
    if(w*h*h<=w*w || w*h*h<=1e9){ //
        init() ;
        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' ;
    }
    else{
        ;
    }
    return 0 ;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…