제출 #586108

#제출 시각아이디문제언어결과실행 시간메모리
586108GusterGoose27Tents (JOI18_tents)C++11
100 / 100
111 ms70704 KiB
#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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...