//#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);
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();
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
112 ms |
9848 KB |
Output is correct |
2 |
Incorrect |
457 ms |
9796 KB |
Output isn't correct |
3 |
Incorrect |
221 ms |
9912 KB |
Output isn't correct |
4 |
Incorrect |
290 ms |
9888 KB |
Output isn't correct |
5 |
Incorrect |
341 ms |
9896 KB |
Output isn't correct |
6 |
Incorrect |
287 ms |
9836 KB |
Output isn't correct |
7 |
Incorrect |
292 ms |
9808 KB |
Output isn't correct |
8 |
Incorrect |
287 ms |
9848 KB |
Output isn't correct |
9 |
Incorrect |
315 ms |
9880 KB |
Output isn't correct |
10 |
Incorrect |
339 ms |
9752 KB |
Output isn't correct |
11 |
Incorrect |
293 ms |
9908 KB |
Output isn't correct |
12 |
Incorrect |
333 ms |
9936 KB |
Output isn't correct |
13 |
Incorrect |
456 ms |
9796 KB |
Output isn't correct |
14 |
Incorrect |
528 ms |
9848 KB |
Output isn't correct |
15 |
Incorrect |
557 ms |
9856 KB |
Output isn't correct |
16 |
Incorrect |
558 ms |
9860 KB |
Output isn't correct |
17 |
Incorrect |
477 ms |
9932 KB |
Output isn't correct |
18 |
Incorrect |
1119 ms |
9904 KB |
Output isn't correct |
19 |
Incorrect |
1115 ms |
9852 KB |
Output isn't correct |
20 |
Incorrect |
561 ms |
9908 KB |
Output isn't correct |