Submission #494849

#TimeUsernameProblemLanguageResultExecution timeMemory
494849NekoRollyTents (JOI18_tents)C++17
100 / 100
96 ms70856 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e3+4;
const int M = 2e2+4;
const int inf = 1e9;
const int mod = 1e9+7;

int n,m;
ll dp[N][N];

ll c2(ll k){
	return (k*k - k)/2 %mod;
}

ll pro(ll a,ll b){
	return (a*b)%mod;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> n >> m;

	for (int i=0; i<=n; i++) dp[i][0] = 1;
	for (int i=0; i<=m; i++) 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] + 4 * j * dp[i-1][j-1];
		if (i >= 2) dp[i][j] += pro(i-1, j) * dp[i-2][j-1];
		if (j >= 2) dp[i][j] += c2(j) * dp[i-1][j-2];
		dp[i][j] %= mod;
	}

	cout << (dp[n][m]+mod-1)%mod << "\n";

	return 0;
}	
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...