Submission #1130211

#TimeUsernameProblemLanguageResultExecution timeMemory
1130211JokerFavTents (JOI18_tents)C++20
100 / 100
92 ms70984 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int const nmax = 3005;
ll const mod = 1e9 + 7;
ll dp[nmax][nmax];
int n, m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for(int i = 0; i <= max(n, m); ++i) dp[i][0] = dp[0][i] = 1;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
        {
            dp[i][j] = dp[i - 1][j];
            dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] * 4 * j) % mod;
            if(j > 1) dp[i][j] = (dp[i][j] + dp[i - 1][j - 2] * j * (j - 1) / 2) % mod;
            if(i > 1) dp[i][j] = (dp[i][j] + dp[i - 2][j - 1] * (i - 1) * j) % mod;
        }
    cout << (dp[n][m] - 1 + mod) % mod;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...