#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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
