제출 #559047

#제출 시각아이디문제언어결과실행 시간메모리
559047groshiTents (JOI18_tents)C++17
100 / 100
233 ms83020 KiB
#include<iostream>

using namespace std;
int mod=1000000007;
long long dp[4000][4000];
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int h,w;
    cin>>h>>w;
    dp[1][1]=1;
    for(int i=2;i<=h+1;i++)
    {
        for(int j=2;j<=w+1;j++)
        {
            if(i==2)
                dp[i][j]=1;
            else dp[i][j]=dp[i-1][j];
            if(i==2 || j==2)
                dp[i][j]+=(j-1)*4;
            else dp[i][j]+=(j-1)*4*dp[i-1][j-1];
            dp[i][j]%=mod;
            if(i==3 || j==2)
                dp[i][j]+=(j-1)*(i-2);
            else dp[i][j]+=(j-1)*(i-2)*dp[i-2][j-1];
            dp[i][j]%=mod;
            if(i==2 || j==3)
                dp[i][j]+=(j-1)*(j-2)/2;
            else dp[i][j]+=((j-1)*(j-2)/2)*dp[i-1][j-2];
            dp[i][j]%=mod;
        }
    }
    cout<<dp[h+1][w+1]-1;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...