Submission #1348489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1348489		branches1029	Lego Wall (EGOI22_legowall)	C++20	62 / 100	1 ms	348 KiB

Main

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

ll w, h;
ll f[800];
ll ans[800];
ll const mod=1e9+7;

ll mod_pw( ll x, ll y ){
    if( y==0 ) return 1LL;
    else if( y==1 ) return x;
    else{
        ll z=mod_pw( x, y/2 );
        z=z*z%mod;
        if( y&1 ) return z*x%mod;
        else return z;
    }
}

int main(){

    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> w >> h;
    assert( w<=700 );

    f[1]=1, f[2]=2;
    for( int i=3 ; i<=w ; i++ ){
        f[i]=(f[i-1]+f[i-2])%mod;
    }
    for( int i=1 ; i<=w ; i++ ){
        f[i]=mod_pw( f[i], h );
    }

    for( int i=1 ; i<=w ; i++ ){
        ans[i]=f[i];
        for( int j=1 ; j<i ; j++ ){
            ll x=ans[j]*f[i-j]%mod;
            ans[i]=( ans[i]-x+mod )%mod;
        }
    }

    cout << ans[w] << '\n';

    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 12
• Subtask 3: 18 / 18
• Subtask 4: 30 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 6