#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
const int N = 6e5 + 100;
int md;
inline int add(int a, int b) { if ((a += b) >= md) a -= md; return a; }
inline void ads(int &a, int b) { if ((a += b) >= md) a -= md; }
inline int sub(int a, int b) { if ((a -= b) < 0) a += md; return a; }
inline void subs(int &a, int b) { if ((a -= b) < 0) a += md; }
inline int mul(int a, int b) { return a * 1ll * b % md; }
inline void muls(int &a, int b) { a = a * 1ll * b % md; }
inline int bp(int a, int n) { int res = 1;
for (; n; n >>= 1, muls(a, a)) {
if (n & 1) muls(res, a);
} return res;
}
int lp[N];
ve<int> pr;
int pw[N][20];
inline void calc() {
for (int i = 2; i < N; ++i) {
if (!lp[i]) lp[i] = i, pr.pb(i);
for (int j = 0; j < sz(pr) && i * pr[j] < N && pr[j] <= lp[i]; ++j) {
lp[i * pr[j]] = pr[j];
}
}
for (int id = 0; id < sz(pr); ++id) {
const int &p = pr[id];
pw[id][0] = 1;
for (int i = 1; i < 20; ++i) pw[id][i] = mul(pw[id][i - 1], p);
}
}
inline int c(int n, int k) {
int answer = 1;
int cnt; ll f; int nk = n - k;
for (int id = 0; id < sz(pr) && pr[id] <= n; ++id) {
const int &p = pr[id]; cnt = 0;
f = p;
while (f <= n) cnt += n / f, f *= p;
f = p;
while (f <= k) cnt -= k / f, f *= p;
f = p;
while (f <= nk) cnt -= nk / f, f *= p;
muls(answer, pw[id][cnt]);
}
return answer;
}
inline void solve() {
#ifndef LOCAL
const string NAME = "turtle";
ifstream cin(NAME + ".in");
ofstream cout(NAME + ".out");
#endif
int n, m, k, t;
cin >> n >> m >> k >> t >> md;
calc();
ve<pii> pts(k);
for (auto &[x, y] : pts) cin >> x >> y;
pts.pb({0, 0}); pts.pb({n, m});
sort(all(pts), [](const pii &a, const pii &b) {
return a.fi + a.se < b.fi + b.se;
});
int s = sz(pts);
ve<ve<int>> cost(s, ve<int> (s));
for (int i = 0; i < s; ++i) {
const auto &[x1, y1] = pts[i];
for (int j = i + 1; j < s; ++j) {
const auto [x2, y2] = pts[j];
if (!(x2 >= x1 && y2 >= y1)) continue;
cost[i][j] = c(x2 - x1 + y2 - y1, x2 - x1);
}
}
ve<int> value(1 << s);
for (int mask = 0; mask < (1 << s); ++mask) {
if ((mask >> 0 & 1 ^ 1) || (mask >> (s - 1) & 1 ^ 1)) continue;
int prev = 0, result = 1;
for (int i = 1; i < s; ++i) {
if (mask >> i & 1 ^ 1) continue;
muls(result, cost[prev][i]);
prev = i;
}
value[mask] = result;
}
for (int i = 0; i < (1 << s); ++i) if (__builtin_popcount(i) & 1) {
value[i] = md - value[i];
}
for (int i = 0; i < s; ++i) {
for (int ma = 0; ma < (1 << s); ++ma) {
if (ma >> i & 1) continue;
ads(value[ma], value[ma ^ (1 << i)]);
}
}
for (int i = 0; i < (1 << s); ++i) if (__builtin_popcount(i) & 1) {
value[i] = md - value[i];
}
int answer = 0;
for (int mask = 0; mask < (1 << s); ++mask) {
if ((mask >> 0 & 1 ^ 1) || (mask >> (s - 1) & 1 ^ 1)) continue;
if (__builtin_popcount(mask) - 2 <= t) {
ads(answer, value[mask]);
}
}
cout << answer;
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int q = 1; // cin >> q;
while (q--) solve();
cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}
Compilation message
turtle.cpp: In function 'void solve()':
turtle.cpp:116:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
116 | if ((mask >> 0 & 1 ^ 1) || (mask >> (s - 1) & 1 ^ 1)) continue;
| ~~~~~~~~~~^~~
turtle.cpp:116:47: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
116 | if ((mask >> 0 & 1 ^ 1) || (mask >> (s - 1) & 1 ^ 1)) continue;
| ~~~~~~~~~~~~~~~~^~~
turtle.cpp:120:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
120 | if (mask >> i & 1 ^ 1) continue;
| ~~~~~~~~~~^~~
turtle.cpp:143:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
143 | if ((mask >> 0 & 1 ^ 1) || (mask >> (s - 1) & 1 ^ 1)) continue;
| ~~~~~~~~~~^~~
turtle.cpp:143:47: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
143 | if ((mask >> 0 & 1 ^ 1) || (mask >> (s - 1) & 1 ^ 1)) continue;
| ~~~~~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
5848 KB |
Execution killed with signal 8 |
| 2 |
Runtime error |
9 ms |
5820 KB |
Execution killed with signal 8 |
| 3 |
Runtime error |
9 ms |
5848 KB |
Execution killed with signal 8 |
| 4 |
Runtime error |
10 ms |
5812 KB |
Execution killed with signal 8 |
| 5 |
Runtime error |
10 ms |
5920 KB |
Execution killed with signal 8 |
| 6 |
Runtime error |
9 ms |
5848 KB |
Execution killed with signal 8 |
| 7 |
Runtime error |
9 ms |
5912 KB |
Execution killed with signal 8 |
| 8 |
Runtime error |
9 ms |
5832 KB |
Execution killed with signal 8 |
| 9 |
Runtime error |
10 ms |
5920 KB |
Execution killed with signal 8 |
| 10 |
Runtime error |
10 ms |
5924 KB |
Execution killed with signal 8 |
| 11 |
Runtime error |
10 ms |
5848 KB |
Execution killed with signal 8 |
| 12 |
Runtime error |
10 ms |
5848 KB |
Execution killed with signal 8 |
| 13 |
Runtime error |
10 ms |
5904 KB |
Execution killed with signal 8 |
| 14 |
Runtime error |
8 ms |
5868 KB |
Execution killed with signal 8 |
| 15 |
Runtime error |
8 ms |
5832 KB |
Execution killed with signal 8 |
| 16 |
Runtime error |
9 ms |
5844 KB |
Execution killed with signal 8 |
| 17 |
Runtime error |
9 ms |
5848 KB |
Execution killed with signal 8 |
| 18 |
Runtime error |
9 ms |
5848 KB |
Execution killed with signal 8 |
| 19 |
Runtime error |
9 ms |
5848 KB |
Execution killed with signal 8 |
| 20 |
Runtime error |
8 ms |
5848 KB |
Execution killed with signal 8 |
