Submission #333482

#	Time	Username	Problem	Language	Result	Execution time	Memory
333482		benson1029	Tents (JOI18_tents)	C++14	100 / 100	186 ms	71020 KiB

tents

#include<bits/stdc++.h>
#define MOD ((long long)1e9+7)
using namespace std;
int n,m;
long long dp[3005][3005];
int main() {
	cin >> n >> m;
	dp[0][0] = 1LL;
	for(int i=0; i<n; i++) {
		for(int j=0; j<=m; j++) {
			if(j+2<=m) {
				dp[i+1][j+2] += (((m-j)*(m-j-1LL)/2)%MOD) * dp[i][j];
				dp[i+1][j+2] %= MOD;
			}
			if(j<m) {
				dp[i+1][j+1] += dp[i][j] * (m-j) * 4LL;
				dp[i+1][j+1] %= MOD;
			}
			if(i<n-1) {
				dp[i+2][j+1] += dp[i][j] * ((((long long)m-j)*(i+1))%MOD);
				dp[i+2][j+1] %= MOD;
			}
		}
		for(int j=0; j<=m; j++) {
			dp[i+1][j] += dp[i][j];
			dp[i+1][j] %= MOD;
		}
	}
	long long ans = 0;
	for(int j=1; j<=m; j++) {
		ans += dp[n][j];
	}
	cout << ans%MOD << endl;
}

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