oj.uz

답안 #248834

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
248834 2020-07-13T14:24:58 Z srvlt 힘 센 거북 (IZhO11_turtle) C++14
100 / 100
 214 ms 9976 KB 
#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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 9848 KB Output is correct
2 Correct 107 ms 9812 KB Output is correct
3 Correct 52 ms 7436 KB Output is correct
4 Correct 58 ms 7416 KB Output is correct
5 Correct 69 ms 7420 KB Output is correct
6 Correct 57 ms 7420 KB Output is correct
7 Correct 58 ms 7416 KB Output is correct
8 Correct 57 ms 7416 KB Output is correct
9 Correct 62 ms 7416 KB Output is correct
10 Correct 67 ms 7416 KB Output is correct
11 Correct 58 ms 7416 KB Output is correct
12 Correct 66 ms 7416 KB Output is correct
13 Correct 108 ms 9848 KB Output is correct
14 Correct 120 ms 9848 KB Output is correct
15 Correct 128 ms 9848 KB Output is correct
16 Correct 128 ms 9848 KB Output is correct
17 Correct 112 ms 9848 KB Output is correct
18 Correct 208 ms 9852 KB Output is correct
19 Correct 214 ms 9976 KB Output is correct
20 Correct 124 ms 9848 KB Output is correct