Submission #72572

#	Time	Username	Problem	Language	Result	Execution time	Memory
72572		Abelyan	Construction of Highway (JOI18_construction)	C++17	0 / 100	129 ms	141944 KiB

construction

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <queue>
#include <map>
#include <set>
#include <cmath>
using namespace std;

typedef long long ll;
const int N = 3006;
const ll MOD = 1000000007;
ll dp[N][N];

ll solve(ll n,ll m) {
	//cout << n << " " << m << endl;
	if (n < 0 | m < 0) return 0;
	if (n == 0 || m == 0) return 1;
	if (dp[n][m]!=-1) return dp[n][m];
	ll ans = 4ll*solve(n-1ll,m-1ll)+4ll*(n-1ll)*solve(n-2ll,m-1ll)+4ll*(m-1ll)*solve(n-1ll,m-2ll)+solve(n-1,m-1)+(n-1)*(m-1)*16ll;
	ans %= MOD;
	ans += (n-1ll)*(m-1ll)*(solve(n-2ll,m-2ll)+solve(n-2ll,m-2ll));
	ans %= MOD;
	ans += (n-1ll)*(m-1ll)*(n - 2ll)*(m - 2ll)*solve(n-3ll,m-3ll);
	ans %= MOD;
	ans += (n - 1ll)*solve(n - 2ll, m - 1ll) + (m - 1ll)*solve(n - 1ll, m - 2ll);
	ans %= MOD;
	ans += (n - 1ll)*(n - 2ll)*solve(n - 3, m - 1) / 2ll + (m - 1ll)*(m - 2ll)*solve(n - 1, m - 3) / 2ll;
	ans %= MOD;
	ans += (m - 1ll)*(m - 2ll)*(n - 1ll)*(n - 2ll)*solve(n - 3, m - 3) / 4ll;
	ans %= MOD;
	ans += 2ll * (n - 1ll)*(n - 2ll)*(m - 1ll)*solve(n - 3, m - 2) + 2ll * (m - 1ll)*(m - 2ll)*(n - 1ll)*solve(n - 2, m - 3);
	ans %= MOD;
	ans += 2ll * (n - 1ll)*(n - 2ll)*(m - 1ll)*(n-3ll)*solve(n - 4, m - 2) + 2ll * (m - 1ll)*(m - 2ll)*(n - 1ll)*(m-3ll)*solve(n - 2, m - 4);
	ans %= MOD;
	return dp[n][m]=ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	int n,m;
	cin >> n >> m;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			dp[i][j] = -1;
		}
	}
	cout<<solve(n,m)-1<<endl;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}
	system("pause");
	return 0;
}

Compilation message (stderr)

construction.cpp: In function 'll solve(ll, ll)':
construction.cpp:18:8: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
  if (n < 0 | m < 0) return 0;
      ~~^~~
construction.cpp: In function 'int main()':
construction.cpp:56:8: warning: ignoring return value of 'int system(const char*)', declared with attribute warn_unused_result [-Wunused-result]
  system("pause");
  ~~~~~~^~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 9
• Subtask 3: 0 / 84