Submission #655165

#	Time	Username	Problem	Language	Result	Execution time	Memory
655165		ParsaS	Tents (JOI18_tents)	C++14	100 / 100	107 ms	35548 KiB

tents

// In the name of God
#pragma GCC optimize("O2", "unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
typedef long long ll;
const int N = 3000 + 5, MOD = 1e9 + 7;
int n, m;
int dp[N][N];

int C2(int i) {
    return 1LL * i * (i - 1) / 2 % MOD;
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        dp[i][1] = (i * 4 + C2(i) + 1) % MOD;
        dp[i][0] = 1;
    }
    for (int i = 1; i <= m; i++) {
        dp[1][i] = (i * 4 + C2(i) + 1) % MOD;
        dp[0][i] = 1;
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];
            dp[i][j] = (dp[i][j] + 4LL * j * dp[i - 1][j - 1] % MOD) % MOD;
            dp[i][j] = (dp[i][j] + 1LL * C2(j) * dp[i - 1][j - 2] % MOD) % MOD;
            dp[i][j] = (dp[i][j] + 1LL * j * (i - 1) % MOD * dp[i - 2][j - 1] % MOD) % MOD;
        }
    }
    cout << (dp[n][m] - 1 + MOD) % MOD;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

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