Submission #1171316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171316		Tob	Tents (JOI18_tents)	C++20	100 / 100	68 ms	35864 KiB

tents

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 3007, mod = 1e9 + 7;

inline int add(int x, int y) {return (x+y<mod ? x+y : x+y-mod);}
inline int mul(int x, int y) {return (ll)x*y%mod;}

int pow(int x, int y) {
	int res = 1, pot = x;
	while (y) {
		if (y % 2) res = mul(res, pot);
		pot = mul(pot, pot);
		y /= 2;
	}
	return res;
}

int pi2[2*N], fac[N], rfac[N], dp[N][N];

int C(int x, int y) {return mul(fac[x], mul(rfac[y], rfac[x-y]));}

int main () {
	FIO;
	pi2[0] = fac[0] = 1;
	pi2[1] = pow(2, mod-2);
	for (int i = 2; i < 2*N; i++) pi2[i] = mul(pi2[i-1], pi2[1]);
	for (int i = 1; i < N; i++) fac[i] = mul(fac[i-1], i);
	rfac[N-1] = pow(fac[N-1], mod-2);
	for (int i = N-1; i; i--) rfac[i-1] = mul(rfac[i], i);
	for (int i = 0; i < N; i++) dp[0][i] = 1;
	for (int i = 1; i < N; i++) {
		for (int j = 1; j < N; j++) {
			dp[i][j] = add(mul(dp[i-1][j-1], 4*j), dp[i-1][j]);
		}
		dp[i][0] = 1;
	}
	
	int n, m; cin >> n >> m;
	int res = 0;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			if (n-i-2*j < 0 || m-2*i-j < 0) continue;
			int c = max(n-i-2*j, m-2*i-j), d = min(n-i-2*j, m-2*i-j);
			res = add(res, mul(mul(mul(mul(C(n, i), C(m-2*i, j)), mul(mul(fac[m], rfac[m-2*i]), mul(fac[n-i], rfac[n-i-2*j]))), pi2[i+j]), dp[d][c]));
		}
	}
	cout << add(res, mod-1);

	return 0;
}

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