Submission #248834

#	Time	Username	Problem	Language	Result	Execution time	Memory
248834		srvlt	Energetic turtle (IZhO11_turtle)	C++14	100 / 100	214 ms	9976 KiB

turtle

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
constexpr int n0 = 6e5 + 123, k0 = 23, m0 = 50000;
int n, m, k, t, z, f[k0], cf[k0], ways[k0][k0], g[n0], fact[11][n0], phi;
array <int, 2> p[k0];
vector <int> F;

int bp(int x, int y, int mod) {
	int res = 1;
	while (y) {
		if (y & 1) res = (ll)res * x % mod;
		x = (ll)x * x % mod;
		y /= 2;
	}
	return res;
}

int binomial(int x, int y) {
	if (y > x) return 0;
	int res = 1;
	for (int i = 1; i <= SZ(F); i++) {
		int pw = fact[i][x] - fact[i][y] - fact[i][x - y];
		if (pw > 0) {
			res = (ll)res * bp(F[i - 1], pw, z) % z;
		}	else {
			res = (ll)res * bp(bp(F[i - 1], phi - 1, z), pw, z) % z;
		}
	}
	res = (((ll)res * fact[0][x] % z) * bp(fact[0][y], phi - 1, z) % z) * bp(fact[0][x - y], phi - 1, z) % z;
	return res;
}
 
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	cin >> n >> m >> k >> t >> z;
	if (z == 1) return cout << 0, 0;
	vector <bool> prime(m0, true);
	prime[0] = prime[1] = false;
	vector <int> primes;
	for (int i = 2; i < m0; i++) {
		if (prime[i]) primes.pb(i);
		for (int j : primes) {
			if ((ll)i * j >= m0) break;
			prime[i * j] = false;
			if (i % j == 0) break;
		}
	}
	int Z = z;
	for (int p : primes) {
		if (p > Z) break;
		int res = 0;
		while (Z % p == 0) Z /= p, res++;
		if (res) F.pb(p);
	}
	if (Z > 1) F.pb(Z);
	int A = 1, B = 1;
	for (int i : F) A *= (i - 1), B *= i;
	phi = (z / B) * A;
	for (int i = 1; i < n0; i++) {
		int x = i;
		while (true) {
			int G = __gcd(x, z);
			if (G == 1) break;
			x /= G;
		}
		g[i] = x;
	}
	for (int i = 0; i <= SZ(F); i++) {
		if (i == 0) {
			fact[i][0] = 1;
			for (int j = 1; j < n0; j++)
				fact[i][j] = (ll)fact[i][j - 1] * g[j] % z;
		}	else {
			for (int j = 1; j < n0; j++) {
				int res = 0, x = j;
				while (x % F[i - 1] == 0) x /= F[i - 1], res++;
				fact[i][j] = fact[i][j - 1] + res;
			}
		}
	}
	for (int i = 0; i < k; i++) cin >> p[i][0] >> p[i][1];
	sort(p, p + k);
	for (int i = 0; i <= k + 1; i++) {
		for (int j = i + 1; j <= k + 1; j++) {
			int x = 0, y = 0, x2 = n, y2 = m;
			if (i > 0) x = p[i - 1][0], y = p[i - 1][1];
			if (j < k + 1) x2 = p[j - 1][0], y2 = p[j - 1][1];
			ways[i][j] = binomial(x2 - x + y2 - y, x2 - x);
		}
	}
	for (int mask = 1; mask < (1 << k); mask++) {
		int bad = 0, res = 1, last = -1;
		int b = __builtin_popcount(mask);
		for (int i = 0; i < k; i++) {
			if (mask >> i & 1) {
				if (last != -1 && p[i][1] < p[last][1]) {
					bad = 1;
					break;
				}
				if (last == -1) res = (ll)res * ways[0][i + 1] % z;
				else res = (ll)res * ways[last + 1][i + 1] % z;
				last = i;
			}
		}
		if (bad) continue;
		res = (ll)res * ways[last + 1][k + 1] % z;
		f[b] = (f[b] + res) % z;
	}
	int res = ways[0][k + 1];
	for (int i = t + 1; i <= k; i++) {
		int cur = 0;
		for (int j = t + 1; j < i; j++)
			cur = (cur + (ll)binomial(i, j) * cf[j] % z) % z;
		cf[i] = (z - 1) - cur;
		res = (res + (ll)cf[i] * f[i] % z) % z;
	}
	cout << res;
}

• Subtask 1: 100 / 100