#include "bits/stdc++.h"
#define ll long long
#define int ll
using namespace std;
const int sz = 6e5 + 2;
const int sm = 30;
vector<pair<int, int>> vp;
vector<int> ps;
ll wz[sm][sm];
ll dp[sm][sm];
bool sv[sz];
ll fact[sz], inv_fact[sz];
ll bpw(ll x, ll b, ll z) {
ll r = 1;
while (b) {
if (b & 1)
(r *= x) %= z;
(x *= x) %= z;
b >>= 1;
}
return r;
}
void precompute_factorials(ll z) {
fact[0] = inv_fact[0] = 1;
for (ll i = 1; i < sz; i++) {
fact[i] = fact[i - 1] * i % z;
}
inv_fact[sz - 1] = bpw(fact[sz - 1], z - 2, z); // Fermat's little theorem for inverse
for (ll i = sz - 2; i >= 1; i--) {
inv_fact[i] = inv_fact[i + 1] * (i + 1) % z;
}
}
ll nck(ll n, ll k, ll z) {
if (n < k || n < 0) return 0;
return fact[n] * inv_fact[k] % z * inv_fact[n - k] % z;
}
ll gt(pair<int, int> f, pair<int, int> s, int z) {
int xds = s.first - f.first;
int yds = s.second - f.second;
return nck(xds + yds, yds, z);
}
ll sb(ll a, ll b, ll z) {
return (a + z - b) % z;
}
ll ml(ll a, ll b, ll z) {
return a * b % z;
}
ll ad(ll a, ll b, ll z) {
return (a + b) % z;
}
signed main() {
for (ll i = 2; i < sz; i++) {
if (sv[i]) continue;
ps.push_back(i);
sv[i] = true;
for (ll j = i * i; j < sz; j += i)
sv[j] = true;
}
ll n, m, k, t, z;
cin >> n >> m >> k >> t >> z;
precompute_factorials(z); // Precompute factorials and their inverses modulo z
for (int i = 0; i < k; i++) {
int x, y;
cin >> x >> y;
vp.push_back(make_pair(x, y));
}
vp.push_back(make_pair(0, 0));
vp.push_back(make_pair(n, m));
sort(begin(vp), end(vp));
k = vp.size();
for (int i = 1; i < k; i++) {
for (int j = i - 1; j >= 0; j--) {
wz[j][i] = gt(vp[j], vp[i], z);
for (int l = j + 1; l < i; l++) {
wz[j][i] = sb(wz[j][i], ml(wz[j][l], gt(vp[l], vp[i], z), z), z);
}
}
}
dp[0][0] = 1;
for (int i = 1; i < k; i++) {
for (int l = 1; l <= t + 1; l++) {
for (int j = 0; j < i; j++) {
dp[i][l] = ad(dp[i][l], ml(dp[j][l - 1], wz[j][i], z), z);
}
}
}
ll r = 0;
for (int i = 1; i <= t + 1; i++) {
r = ad(r, dp[k - 1][i], z);
}
cout << r << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
10712 KB |
Output isn't correct |
| 2 |
Incorrect |
12 ms |
10708 KB |
Output isn't correct |
| 3 |
Incorrect |
11 ms |
10728 KB |
Output isn't correct |
| 4 |
Incorrect |
15 ms |
10704 KB |
Output isn't correct |
| 5 |
Incorrect |
11 ms |
10704 KB |
Output isn't correct |
| 6 |
Incorrect |
14 ms |
10708 KB |
Output isn't correct |
| 7 |
Incorrect |
12 ms |
10708 KB |
Output isn't correct |
| 8 |
Incorrect |
13 ms |
10900 KB |
Output isn't correct |
| 9 |
Incorrect |
12 ms |
10932 KB |
Output isn't correct |
| 10 |
Runtime error |
20 ms |
21716 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
20 ms |
21716 KB |
Execution killed with signal 11 |
| 12 |
Incorrect |
10 ms |
10708 KB |
Output isn't correct |
| 13 |
Incorrect |
12 ms |
10864 KB |
Output isn't correct |
| 14 |
Incorrect |
11 ms |
10708 KB |
Output isn't correct |
| 15 |
Incorrect |
13 ms |
10700 KB |
Output isn't correct |
| 16 |
Runtime error |
20 ms |
21700 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
19 ms |
21716 KB |
Execution killed with signal 11 |
| 18 |
Incorrect |
13 ms |
10772 KB |
Output isn't correct |
| 19 |
Incorrect |
10 ms |
10708 KB |
Output isn't correct |
| 20 |
Runtime error |
21 ms |
21596 KB |
Execution killed with signal 11 |
