Submission #961063

#TimeUsernameProblemLanguageResultExecution timeMemory
961063simona1230Tents (JOI18_tents)C++17
100 / 100
71 ms70844 KiB
#include <bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long n,m;
long long dp[3001][3001];
void solve()
{
    cin>>n>>m;

    dp[0][0]=1;
    for(long long i=1;i<=n;i++)
        dp[i][0]=1;
    for(long long i=1;i<=m;i++)
        dp[0][i]=1;
    for(long long i=1;i<=n;i++)
    {
        for(long long j=1;j<=m;j++)
        {
            dp[i][j]=dp[i-1][j];
            dp[i][j]%=mod;
            if(i>=2)dp[i][j]+=dp[i-2][j-1]*j*(i-1);
            dp[i][j]%=mod;
            if(j>=2)dp[i][j]+=dp[i-1][j-2]*(j-1)*j/2;
            dp[i][j]%=mod;
            dp[i][j]+=dp[i-1][j-1]*j*4;
            dp[i][j]%=mod;
            //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
        }
    }
    cout<<dp[n][m]-1<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...