Submission #100456

#	Time	Username	Problem	Language	Result	Execution time	Memory
100456		JPN20	Tents (JOI18_tents)	C++17	100 / 100	784 ms	141944 KiB

tents

#include <bits/stdc++.h>
using namespace std;

long long dp[3009][3009], nr[3009][3009], rem[3009], mod = 1000000007;

long long ncr(long long n, long long r) {
	if (r < 0 || n < r) return 0;
	return nr[n - r][r];
}

void init() {
	for (int i = 0; i <= 3000; i++) {
		for (int j = 0; j <= 3000; j++) {
			if (i == 0 || j == 0) dp[i][j] = 1;
			else dp[i][j] = (1LL * dp[i - 1][j] + 4LL * j * dp[i - 1][j - 1]) % mod;
		}
	}
	for (int i = 0; i <= 3000; i++) {
		for (int j = 0; j <= 3000; j++) {
			if (i == 0 || j == 0) nr[i][j] = 1;
			else nr[i][j] = (nr[i][j - 1] + nr[i - 1][j]) % mod;
		}
	}
	rem[0] = 1;
	for (int i = 1; i <= 1500; i++) {
		rem[i] = rem[i - 1] * ncr(i * 2, 2);
		rem[i] %= mod;
	}
}

long long product(vector<long long>E) {
	long long ans = 1;
	for (int i = 0; i < E.size(); i++) { ans *= E[i]; ans %= mod; }
	return ans;
}

long long H, W, sum;

int main() {
	cin >> H >> W; init();
	for (int i = 0; i <= H / 2; i++) {
		for (int j = 0; j <= W / 2; j++) {
			int c1 = H - i * 2 - j, c2 = W - i - j * 2;
			if (c1 < 0 || c2 < 0) continue;
			
			long long F1 = rem[i];
			long long F2 = rem[j];
			long long F3 = dp[c1][c2];
			long long F4 = ncr(H, i * 2);
			long long F5 = ncr(W, i);
			long long F6 = ncr(H - i * 2, j);
			long long F7 = ncr(W - i, j * 2);
			sum += product({F1, F2, F3, F4, F5, F6, F7});
			sum %= mod;
		}
	}
	cout << sum - 1 << endl;
	return 0;
}

Compilation message (stderr)

tents.cpp: In function 'long long int product(std::vector<long long int>)':
tents.cpp:33:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < E.size(); i++) { ans *= E[i]; ans %= mod; }
                  ~~^~~~~~~~~~

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