#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() {
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:110:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
110 | if ((mask >> 0 & 1 ^ 1) || (mask >> (s - 1) & 1 ^ 1)) continue;
| ~~~~~~~~~~^~~
turtle.cpp:110:47: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
110 | if ((mask >> 0 & 1 ^ 1) || (mask >> (s - 1) & 1 ^ 1)) continue;
| ~~~~~~~~~~~~~~~~^~~
turtle.cpp:114:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
114 | if (mask >> i & 1 ^ 1) continue;
| ~~~~~~~~~~^~~
turtle.cpp:137:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
137 | if ((mask >> 0 & 1 ^ 1) || (mask >> (s - 1) & 1 ^ 1)) continue;
| ~~~~~~~~~~^~~
turtle.cpp:137:47: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
137 | if ((mask >> 0 & 1 ^ 1) || (mask >> (s - 1) & 1 ^ 1)) continue;
| ~~~~~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
6744 KB |
Output is correct |
| 2 |
Correct |
14 ms |
6744 KB |
Output is correct |
| 3 |
Correct |
14 ms |
6776 KB |
Output is correct |
| 4 |
Correct |
20 ms |
7372 KB |
Output is correct |
| 5 |
Correct |
241 ms |
23212 KB |
Output is correct |
| 6 |
Correct |
14 ms |
6744 KB |
Output is correct |
| 7 |
Correct |
27 ms |
7880 KB |
Output is correct |
| 8 |
Correct |
14 ms |
6744 KB |
Output is correct |
| 9 |
Correct |
66 ms |
11008 KB |
Output is correct |
| 10 |
Correct |
122 ms |
15064 KB |
Output is correct |
| 11 |
Correct |
37 ms |
7860 KB |
Output is correct |
| 12 |
Correct |
140 ms |
15048 KB |
Output is correct |
| 13 |
Correct |
25 ms |
6856 KB |
Output is correct |
| 14 |
Correct |
52 ms |
8868 KB |
Output is correct |
| 15 |
Correct |
244 ms |
23252 KB |
Output is correct |
| 16 |
Correct |
285 ms |
23256 KB |
Output is correct |
| 17 |
Correct |
88 ms |
10832 KB |
Output is correct |
| 18 |
Correct |
268 ms |
23332 KB |
Output is correct |
| 19 |
Correct |
257 ms |
23252 KB |
Output is correct |
| 20 |
Correct |
248 ms |
23260 KB |
Output is correct |
