Submission #494849

#	Time	Username	Problem	Language	Result	Execution time	Memory
494849		NekoRolly	Tents (JOI18_tents)	C++17	100 / 100	96 ms	70856 KiB

tents

#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;
}	

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