//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], phi;
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) {
int res = 1;
for (int i = 1; i <= a; i++) {
res = res * (b - a + i) / i;
res %= z;
}
return res;
}
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;
}
}
}
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();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
9848 KB |
Output is correct |
| 2 |
Incorrect |
457 ms |
9952 KB |
Output isn't correct |
| 3 |
Incorrect |
222 ms |
9844 KB |
Output isn't correct |
| 4 |
Incorrect |
331 ms |
9816 KB |
Output isn't correct |
| 5 |
Execution timed out |
2043 ms |
9844 KB |
Time limit exceeded |
| 6 |
Incorrect |
332 ms |
9900 KB |
Output isn't correct |
| 7 |
Incorrect |
666 ms |
9848 KB |
Output isn't correct |
| 8 |
Incorrect |
301 ms |
9848 KB |
Output isn't correct |
| 9 |
Execution timed out |
2043 ms |
9880 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2020 ms |
9832 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2076 ms |
9848 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2103 ms |
9912 KB |
Time limit exceeded |
| 13 |
Incorrect |
1467 ms |
9888 KB |
Output isn't correct |
| 14 |
Execution timed out |
2061 ms |
9848 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2011 ms |
9844 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2019 ms |
9916 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2027 ms |
9760 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2040 ms |
9844 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2041 ms |
9908 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2059 ms |
9916 KB |
Time limit exceeded |
