제출 #1316026

#제출 시각아이디문제언어결과실행 시간메모리
1316026mat_jurTents (JOI18_tents)C++20
100 / 100
1315 ms35784 KiB
#include "bits/stdc++.h"
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

const int mod = 1'000'000'007;

int add(int a, int b) {
	a += b;
	return a >= mod ? a-mod : a;
}

int sub(int a, int b) {
	return add(a, mod-b);
}

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

int fpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b&1) {
			res = mul(a, res); 
			b--;
		}
		a = mul(a, a);
		b /= 2;
	}
	return res;
}

int inv(int x) {
	return fpow(x, mod-2);
}


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

	int n, m;
	cin >> n >> m;
	vector<vector<int>> dp(n+1, vector<int>(m+1, 1));

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			dp[i][j] = 0;
			if (i-2 >= 0 && j-1 >= 0) dp[i][j] = add(dp[i][j], 
					mul(mul(i, mul(i-1, inv(2))), dp[i-2][j-1]));
			if (i-1 >= 0 && j-2 >= 0) dp[i][j] = add(dp[i][j], 
					mul(i, mul(j-1, dp[i-1][j-2])));
			dp[i][j] = add(dp[i][j], mul(4*i, dp[i-1][j-1]));
			dp[i][j] = add(dp[i][j], dp[i][j-1]);
		}
	}

	debug(dp);
	
	cout << sub(dp[n][m], 1) << '\n';
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...