제출 #46775

#제출 시각아이디문제언어결과실행 시간메모리
46775kyleliuTents (JOI18_tents)C++14
100 / 100
238 ms71460 KiB
#include <bits/stdc++.h> // PLEASE

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pp;
#define MAXN 3005
#define MAXM 1005
#define MAXP 25
#define A first
#define B second
#define MP make_pair
#define PB push_back
const ll INF = 2e9+13;
const ll MOD = 1e9+7;
ll mmul(ll a, ll b) { return (a*b)%MOD; }
ll madd(ll a, ll b) { return (a+b)%MOD; }
void up(ll &a, ll b) { a = madd(a, b); }
	
int N, M;
ll dp[MAXN][MAXN];
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> M >> N;
	
	for(int i=0; i<=M; i++) dp[i][0] = 1;
	for(int i=0; i<=N; i++) dp[0][i] = 1;
	for(int i=1; i<=M; i++) for(int j=1; j<=N; j++) {
		up(dp[i][j], dp[i-1][j]);
		up(dp[i][j], mmul(mmul(4LL, j), dp[i-1][j-1]));
		if(i > 1) up(dp[i][j], mmul(mmul(i-1, j), dp[i-2][j-1]));
		if(j > 1) up(dp[i][j], mmul((((j-1LL)*j)/2LL)%MOD, dp[i-1][j-2]));
	}
	cout << madd(dp[M][N], MOD-1) << endl;

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...