Submission #1088582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088582		DobromirAngelov	Tents (JOI18_tents)	C++14	100 / 100	92 ms	70932 KiB

tents

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int MOD=1e9+7;
const int MAXN=3005;

int h,w;
long long dp[MAXN][MAXN];
long long fact[MAXN];
long long invF[MAXN];

int fastPow(long long x,int pwr)
{
    long long ret=1;
    while(pwr>0)
    {
        if(pwr&1) ret=ret*x%MOD;
        pwr/=2;
        x=x*x%MOD;
    }
    return ret;
}

int inverse(int x)
{
    return fastPow(x,MOD-2);
}

void precomp()
{
    for(int i=0;i<=w;i++) dp[0][i]=1;
    for(int i=0;i<=h;i++) dp[i][0]=1;
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            dp[i][j]=(dp[i][j-1]+i*dp[i-1][j-1]*4)%MOD;
        }
    }

    fact[0]=1;
    for(int i=1;i<MAXN;i++) fact[i]=fact[i-1]*i%MOD;
    for(int i=0;i<MAXN;i++) invF[i]=inverse(fact[i]);
}

int comb(int n,int k)
{
    return (fact[n]*invF[n-k]%MOD)*invF[k]%MOD;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>h>>w;

    precomp();

    long long ans=0;
    long long P1=1;
    for(int r=0;r<=min(h,w/2);r++)
    {
        long long cur1=comb(h,r);
        if(r>0) P1=P1*comb(w-2*r+2,2)%MOD;
        cur1=cur1*P1%MOD;
        long long P2=1;
        for(int c=0;c<=min((h-r)/2,w-2*r);c++)
        {
            long long cur2=cur1*comb(w-2*r,c)%MOD;
            if(c>0) P2=P2*comb(h-r-2*c+2,2)%MOD;
            cur2=cur2*P2%MOD;

            cur2=cur2*dp[h-r-2*c][w-2*r-c]%MOD;
            ans+=cur2;
            if(ans>=MOD) ans-=MOD;
        }
    }

    cout<<ans-1<<endl;

    return 0;
}

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