//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 = 700000;
int n, m, k, t, z, ans, 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 >>= 1LL;
}
return res;
}
int c(int a, int b) {
if (a < 0) {
return 0;
}
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);
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 < (1LL << k); i++) {
int sgn = 1;
if (__builtin_popcountll(i) > t) {
sgn = -1;
}
pii last = {0, 0};
int res = 1;
bool wrong = false;
for (int j = 0; j < k; j++) {
if (i & (1LL << j)) {
int dx = v[j].fi - last.fi + 1, dy = v[j].se - last.se + 1;
if (v[j].fi < last.fi || v[j].se < last.se) {
wrong = true;
break;
}
int tmp = c(dx - 2, dx + dy - 3) + c(dx - 1, dx + dy - 3);
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 |
6 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 3 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 4 |
Incorrect |
53 ms |
600 KB |
Output isn't correct |
| 5 |
Execution timed out |
2005 ms |
376 KB |
Time limit exceeded |
| 6 |
Incorrect |
82 ms |
376 KB |
Output isn't correct |
| 7 |
Incorrect |
751 ms |
504 KB |
Output isn't correct |
| 8 |
Incorrect |
37 ms |
376 KB |
Output isn't correct |
| 9 |
Execution timed out |
2055 ms |
376 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2065 ms |
376 KB |
Time limit exceeded |
| 11 |
Execution timed out |
2083 ms |
376 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2005 ms |
504 KB |
Time limit exceeded |
| 13 |
Incorrect |
1595 ms |
476 KB |
Output isn't correct |
| 14 |
Execution timed out |
2011 ms |
376 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2069 ms |
504 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2025 ms |
424 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2062 ms |
376 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2012 ms |
476 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2080 ms |
248 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2074 ms |
376 KB |
Time limit exceeded |
