Submission #44482

#	Time	Username	Problem	Language	Result	Execution time	Memory
44482		aome	Tents (JOI18_tents)	C++17	100 / 100	200 ms	35968 KiB

tents

#include <bits/stdc++.h>

using namespace std;

const int N = 3005;
const int mod = 1e9 + 7;

int n, m, f[N][N];

void add(int &x, int y) {
	x += x + y >= mod ? y - mod : y;
}

int main() {
	cin >> n >> m;
	f[n][m] = 1;
	for (int i = n; i >= 0; --i) {
		for (int j = m; j >= 0; --j) {
			if (j) {
				add(f[i][j - 1], f[i][j]);
				if (i) add(f[i - 1][j - 1], 4LL * f[i][j] * i % mod);
				if (i > 1) {
					add(f[i - 2][j - 1], 1LL * f[i][j] * i * (i - 1) / 2 % mod);
				}
				if (i && j > 1) {
					add(f[i - 1][j - 2], 1LL * f[i][j] * i * (j - 1) % mod);
				}
			}
			else if (i) add(f[i - 1][j], f[i][j]);
		}
	}
	cout << (f[0][0] + mod - 1) % mod;
}

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