Submission #87067

#	Time	Username	Problem	Language	Result	Execution time	Memory
87067		Just_Solve_The_Problem	Energetic turtle (IZhO11_turtle)	C++11	5 / 100	733 ms	5368 KiB

turtle

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = (int)3e5 + 7;

int mod;
int cnt[N], lp[N];

int mult(int a, int b) {
	return (a * 1LL * b) % mod;
}

int add(int a, int b) {
	return (a + b) % mod;
}

void precalc() {
	for (int i = 2; i < N; i++) {
		if (lp[i]) continue;
		for (int j = i; j < N; j += i) {
			if (!lp[j]) {
				lp[j] = i;
			}
		}
 	}
}

void add1(int x, int val) {
	while (x > 1) {
		cnt[lp[x]] += val;
		x /= lp[x];
	}
}

int calc(int n, int k) {
	int res = 1;
	for (int i = 2; i <= n; i++) {
		add1(i, 1);
	}
	for (int i = 2; i <= k; i++) {
		add1(i, -1);
	}
	for (int i = 2; i <= n - k; i++) {
		add1(i, -1);
	}
	for (int i = 2; i <= n; i++) {
		while (cnt[i] > 0) {
			res = mult(res, i);
			cnt[i]--;
		}
	}
	return res;
}

int n, m, k, t;
int dp[22][22];
pair < int, int > ar[22];

main() {
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	//cout.tie(0);
	precalc();
	cin >> n >> m >> k >> t >> mod;
	n++; m++;
	for (int i = 1; i <= k; i++) {
		cin >> ar[i].first >> ar[i].second;
		ar[i].first++;
		ar[i].second++;
	}
	sort(ar + 1, ar + k + 1);
	for (int i = 1; i <= k; i++) {
		dp[1][i] = calc(ar[i].first + ar[i].second - 2, ar[i].first - 1);
	}
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j < i; j++) {
			if (ar[j].second <= ar[i].second) {
				dp[1][i] = add(dp[1][i], mod - mult(dp[1][j], calc(abs(ar[j].second - ar[i].second) + abs(ar[i].first - ar[j].first), abs(ar[i].first - ar[j].first))));
			}
		}
	}
	int ans = calc(n + m - 2, n - 1);
	for (int i = 1; i <= k; i++) {
		ans = add(ans, mod - mult(calc(n - ar[i].first + m - ar[i].second, n - ar[i].first), dp[1][i]));
	}
	cout << ans << endl;
}
/*
5 5 3 4 1000000000
2 2
2 3
3 3
*/

Compilation message (stderr)

turtle.cpp:62:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

• Subtask 1: 5 / 100