Submission #55464

#	Time	Username	Problem	Language	Result	Execution time	Memory
55464		szawinis	Tents (JOI18_tents)	C++17	100 / 100	167 ms	71348 KiB

tents

#include <bits/stdc++.h>
using namespace std;
#define fori(i, a, b) for(int i = (int) a; i <= (int) b; ++i)
#define rofi(i, b, a) for(int i = (int) b; i >= (int) a; --i)
#define foreach(tt, a) for(auto &tt: a)
#define all(a) begin(a), end(a)
#define csz(a) (int) a.size()
#define pb push_back
#define epb emplace_back
#define mp make_pair
#define load(a, v) fill(begin(a), end(a), v)
#define load_mem(a, v) memset(a, v, sizeof(a));
#define iostream_optimize() ios::sync_with_stdio(false); cin.tie(0);
using ll = long long;
const ll MOD = 1e9+7, LINF = 1e16+1;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const ll P1 = 31, P2 = 37, M1 = 1e9+7, M2 = 1e9+9;

// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/* <<<<<<<<<<<<<<<<<<<<<<<<<<<< END TEMPLATE >>>>>>>>>>>>>>>>>>>>>>>>>>> */
const int N = 3001;

int n, m, fact[N], inv[N];
ll ans, dp[N][N];

void add(ll& a, ll b) {
	a = a + b;
	if(a >= MOD) a -= MOD;
}

ll mul(ll a, ll b) {
	a *= b;
	if(a >= MOD) a %= MOD;
	return a;
}

ll modPow(ll b, ll e) {
	if(e == 0) return 1;
	if(e == 1) return b;
	return mul(modPow(mul(b, b), e >> 1), modPow(b, e & 1));
}

ll C(ll n, ll k) {
	return mul(fact[n], mul(inv[k], inv[n-k]));
}

int main() {
	iostream_optimize();
	fact[0] = inv[0] = 1;
	fori(i, 1, N-1) {
		fact[i] = mul(fact[i-1], i);
		inv[i] = modPow(fact[i], MOD-2);
	}

	cin >> n >> m;

	fori(j, 0, n) dp[0][j] = 1;
	fori(i, 1, m) {
		fori(j, 0, n) {
			add(dp[i][j], dp[i-1][j]);
			if(j > 0) add(dp[i][j], mul(dp[i-1][j-1], j*4));
			if(j > 1) add(dp[i][j], mul(dp[i-1][j-2], j*(j-1)/2));
		}
	}
	fori(k, 0, min(n, m >> 1)) {
		ll combi = mul(C(n, k), C(m, k << 1));
		combi = mul(combi, mul(fact[k << 1], modPow(inv[2], k)));
		add(ans, mul(dp[m-(k << 1)][n-k], combi));
	}
	cout << (ans-1+MOD) % MOD;
}

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