제출 #1343607

#제출 시각아이디문제언어결과실행 시간메모리
1343607khanhphucscratchTents (JOI18_tents)C++20
100 / 100
200 ms70852 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
int dp[3005][3005], cd[3005][3005];
signed main()
{
    int n, m; cin>>n>>m;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++) if(i*j == 0) dp[i][j] = 1;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            //Nothing in the last col
            dp[i][j] = (dp[i][j] + dp[i][j-1])%mod;
            //One single row, and one col
            dp[i][j] = (dp[i][j] + 4*i*dp[i-1][j-1])%mod;
            //One row, two col
            if(j >= 2) dp[i][j] = (dp[i][j] + dp[i-1][j-2]*i*(j-1))%mod;
            //Two row, one col
            if(i >= 2) dp[i][j] = (dp[i][j] + dp[i-2][j-1] * i * (i-1) / 2)%mod;
            //cerr<<"A"<<i<<" "<<j<<" "<<dp[i][j]<<endl;
        }
    }
    cout<<(dp[n][m]-1+mod)%mod;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...