//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define int long long
using namespace std;
void dout() {
cerr << endl;
}
template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
cerr << H << ' ';
dout(T...);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;
const int M = 600000;
int n, m, k, t, z, ans, f[M + 3], fr[M + 3];
vector <pii> v;
vector <bool> prime(M + 3, true);
int binpow(int x, int y) {
int res = 1;
while (y > 0) {
if (y & 1) {
res = res * x % z;
}
x = x * x % z;
y >>= 1;
}
return res;
}
int c(int a, int b) {
return (f[b] * fr[a] % z) * fr[b - a] % z;
}
int getphi(int x) {
if (x == 1) {
return 1;
}
for (int i = 2; i * i <= x; i++) {
if (prime[i] && x % i == 0) {
int tmp = 1;
while (x > 1 && x % i == 0) {
tmp *= i;
x /= i;
}
tmp /= i;
return getphi(x) * tmp * (i - 1) % z;
}
}
return (x - 1) % z;
}
void solve(int tc) {
cin >> n >> m >> k >> t >> z;
prime[0] = prime[1] = false;
for (int i = 2; i <= M; i++) {
if (prime[i]) {
for (int j = i * i; j <= M; j += i) {
prime[j] = false;
}
}
}
int phi = getphi(z);
dout("phi", phi);
f[0] = fr[0] = 1;
for (int i = 1; i <= M; i++) {
f[i] = f[i - 1] * i % z;
fr[i] = fr[i - 1] * binpow(i, phi - 1) % z;
}
for (int i = 0; i < k; i++) {
pii p;
cin >> p.fi >> p.se;
v.pb(p);
}
sort(v.begin(), v.end());
for (int i = 0; i < (1 << k); i++) {
int sgn = 1;
if (__builtin_popcount(i) > t) {
sgn = -1;
}
pii last = {0, 0};
int res = 1;
bool wrong = false;
for (int j = 0; j < k; j++) {
if (i & (1 << j)) {
int dx = v[j].fi - last.fi + 1, dy = v[j].se - last.se + 1;
if (dy < 1) {
wrong = true;
break;
}
int tmp = c(dx - 1, dx + dy - 2);
res = res * tmp % z;
last = v[j];
}
}
if (wrong) {
continue;
}
int dx = n - last.fi + 1, dy = m - last.se + 1;
int tmp = c(dx - 1, dx + dy - 2);
res = res * tmp % z;
ans = (ans + res * sgn + z) % z;
}
cout << ans;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int tc = 1;
// cin >> tc;
for (int i = 0; i < tc; i++) {
solve(i);
// cleanup();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
9924 KB |
Output isn't correct |
| 2 |
Incorrect |
455 ms |
9860 KB |
Output isn't correct |
| 3 |
Incorrect |
220 ms |
9848 KB |
Output isn't correct |
| 4 |
Incorrect |
291 ms |
9796 KB |
Output isn't correct |
| 5 |
Incorrect |
350 ms |
9848 KB |
Output isn't correct |
| 6 |
Incorrect |
296 ms |
9848 KB |
Output isn't correct |
| 7 |
Incorrect |
302 ms |
9848 KB |
Output isn't correct |
| 8 |
Incorrect |
287 ms |
9848 KB |
Output isn't correct |
| 9 |
Incorrect |
317 ms |
9776 KB |
Output isn't correct |
| 10 |
Incorrect |
340 ms |
9852 KB |
Output isn't correct |
| 11 |
Incorrect |
303 ms |
9792 KB |
Output isn't correct |
| 12 |
Incorrect |
336 ms |
9736 KB |
Output isn't correct |
| 13 |
Incorrect |
458 ms |
9728 KB |
Output isn't correct |
| 14 |
Incorrect |
531 ms |
9872 KB |
Output isn't correct |
| 15 |
Incorrect |
557 ms |
9800 KB |
Output isn't correct |
| 16 |
Incorrect |
554 ms |
9740 KB |
Output isn't correct |
| 17 |
Incorrect |
479 ms |
9916 KB |
Output isn't correct |
| 18 |
Incorrect |
1122 ms |
9812 KB |
Output isn't correct |
| 19 |
Incorrect |
1162 ms |
9848 KB |
Output isn't correct |
| 20 |
Incorrect |
531 ms |
9748 KB |
Output isn't correct |
