Submission #1184758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184758		mareksb	Tents (JOI18_tents)	C++20	100 / 100	151 ms	59116 KiB

tents

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;
const int64_t MOD=1e9+7;
const int64_t N=3005;
int64_t h,w;
int64_t fac[N];
int64_t ifac[N];
int64_t pow2[N];
int64_t ipow2[N];
int64_t dp[N][N];
int64_t binexp(int64_t n, int64_t k){
    int ans=1;
    while(k>0){
        if(k%2==1){
            ans=(ans*n)%MOD;
        }
        n=(n*n)%MOD;
        k/=2;
    }
    return ans;
}
int64_t inv(int64_t n){
    return binexp(n,MOD-2);
}
int64_t c(int64_t n, int64_t k){
    return (((fac[n]*ifac[k])%MOD)*ifac[k-1])%MOD;
}
int64_t fdp(int64_t n, int64_t m){
    if(dp[n][m])return dp[n][m];
    if(n<=0||m<=0)return 1;
    //no tent in row
    int64_t ans=fdp(n-1,m);
    //place one tent in row (m column choice)
    ans=(ans+fdp(n-1,m-1)*4*m)%MOD;
    //place two tents in column (one in cur row) (m columns, then n-1 free rows)
    ans=(ans+fdp(n-2,m-1)*m*(n-1))%MOD;
    //place two tents in row (one in cur column) (m columns, then m-1 free columns) (dependent so we divide by two)
    ans=(ans+fdp(n-1,m-2)*m*(m-1)/2)%MOD;
    dp[n][m]=ans;
    return ans;
}
void solve() {
    
    cin>>h>>w;
    fac[0]=1;
    pow2[0]=1;
    for(int i=1;i<N;i++){
        fac[i]=(fac[i-1]*i)%MOD;
        pow2[i]=(pow2[i-1]*2)%MOD;
    }
    ifac[N-1]=inv(fac[N-1]);
    ipow2[N-1]=inv(pow2[N-1]);
    for(int i=N-2;i>=0;i--){
        ifac[i]=(ifac[i+1]*(i+1))%MOD;
        ipow2[i]=(ipow2[i+1]*2)%MOD;
    }

    int64_t ans=(fdp(h,w)-1)%MOD;
    cout<<ans<<'\n';

}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
    int64_t t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52