Submission #586108

#	Time	Username	Problem	Language	Result	Execution time	Memory
586108		GusterGoose27	Tents (JOI18_tents)	C++11	100 / 100	111 ms	70704 KiB

tents

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 3000;
const int MOD = 1e9+7;
ll dp[MAXN+1][MAXN+1];
ll n, m;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for (ll i = 0; i <= n; i++) {
		for (ll j = 0; j <= m; j++) {
			if (i == 0 || j == 0) {
				dp[i][j] = 1;
				continue;
			}
			ll m1 = j*(i-1);
			m1 %= MOD;
			ll m2 = j*(j-1)/2;
			m2 %= MOD;
			dp[i][j] += 4*j*dp[i-1][j-1];
			dp[i][j] %= MOD;
			dp[i][j] += dp[i-1][j];
			dp[i][j] %= MOD;
			if (j > 1) dp[i][j] += m2*dp[i-1][j-2];
			dp[i][j] %= MOD;
			if (i > 1) dp[i][j] += m1*dp[i-2][j-1];
			dp[i][j] %= MOD;
		}
	}
	cout << ((dp[n][m]-1+MOD)%MOD) << "\n";
}

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