#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int a[25], b[25], c[600005][10], d[600005][10];
long long int f[600005][10], g[600005][10], p[600005][10], dd[25][25], z;
vector<pair<int, int>> v;
vector<int> vv, va;
long long int power(long long int x, long long int y, long long int mod = z) {
long long int res = 1, h = x;
while (y) {
if (y & 1) res = res * h % mod;
h = h * h % mod;
y >>= 1;
}
return res;
}
long long int C(long long int n, long long int k) {
vector<long long int> res;
for (int i = 0; i < v.size(); i++) {
int h = c[n][i] - c[k][i] - c[n - k][i];
if (h >= v[i].second) {
res.push_back(0);
continue;
}
res.push_back(f[n][i] * g[k][i] % vv[i] * g[n - k][i] % vv[i] * p[h][i] % vv[i]);
}
long long int h = 0;
for (int i = 0; i < v.size(); i++) {
long long int k = z / vv[i];
h = (h + res[i] * k % z * va[i]) % z;
}
return h;
}
bool check(int i, int j) {
if (a[i] > a[j] || b[i] > b[j]) return false;
return true;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m, k, t, l;
cin >> n >> m >> k >> t >> z;
for (int i = 1; i <= k; i++) {
cin >> a[i] >> b[i];
v.push_back({a[i], b[i]});
}
sort(v.begin(), v.end());
for (int i = 1; i <= k; i++) {
a[i] = v[i - 1].first;
b[i] = v[i - 1].second;
}
v.clear();
l = z;
int h = sqrt(z);
for (int i = 2; i <= h; i++) {
if (z % i == 0) {
int c = 0;
while (z % i == 0) {
c++;
z /= i;
}
v.push_back({i, c});
int h = power(i, c, l);
if (h == 0) h = l;
vv.push_back(h);
}
}
if (z != 1) v.push_back({z, 1}), vv.push_back(z);
z = l;
for (int i = 1; i <= n + m; i++) {
for (int j = 0; j < v.size(); j++) {
long long int h = v[j].first;
while (h <= i) {
c[i][j] += i / h;
h *= v[j].first;
}
int k = i;
while (k % v[j].first == 0) {
k /= v[j].first;
}
d[i][j] = k;
}
}
for (int j = 0; j < v.size(); j++) {
va.push_back(power(z / vv[j], vv[j] - 2, vv[j]));
f[0][j] = 1;
for (int i = 1; i <= n + m; i++) {
f[i][j] = f[i - 1][j] * d[i][j] % vv[j];
}
g[n + m][j] = power(f[n + m][j], vv[j] - 2, vv[j]);
for (int i = n + m - 1; i >= 0; i--) {
g[i][j] = g[i + 1][j] * d[i + 1][j] % vv[j];
}
p[0][j] = 1;
for (int i = 1; i <= n + m; i++) {
p[i][j] = 1ll * p[i - 1][j] * v[j].first % vv[j];
}
}
a[k + 1] = n, b[k + 1] = m;
k++;
for (int i = 0; i < k; i++) {
if (!check(i, i + 1)) continue;
dd[i][i + 1] = C(a[i + 1] - a[i] + b[i + 1] - b[i], a[i + 1] - a[i]);
}
for (int d = 3; d <= k + 1; d++) {
for (int i = 0; i <= k - d + 1; i++) {
int j = i + d - 1;
if (!check(i, j)) continue;
dd[i][j] = C(a[j] - a[i] + b[j] - b[i], a[j] - a[i]);
for (int l = i + 1; l < j; l++) {
if (!check(i, l)) continue;
dd[i][j] = (dd[i][j] + z - C(a[l] - a[i] + b[l] - b[i], a[l] - a[i]) * dd[l][j] % z) % z;
}
}
}
long long int res = 0;
for (int i = 0; i < (1 << (k + 1)); i++) {
int h = __builtin_popcount(i);
if (h > t + 2) continue;
if (!(i & 1) || !(i & (1 << k))) continue;
vector<int> v;
long long int c = 1;
for (int j = 0; j <= k; j++) {
if (i & (1 << j)) {
v.push_back(j);
}
}
for (int i = 1; i < v.size(); i++) {
c *= dd[v[i - 1]][v[i]];
c %= z;
}
res = (res + c) % z;
}
cout << res;
}
Compilation message
turtle.cpp: In function 'long long int C(long long int, long long int)':
turtle.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
turtle.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
turtle.cpp: In function 'int main()':
turtle.cpp:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int j = 0; j < v.size(); j++) {
| ~~^~~~~~~~~~
turtle.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for (int j = 0; j < v.size(); j++) {
| ~~^~~~~~~~~~
turtle.cpp:130:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for (int i = 1; i < v.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
7 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
260 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 7 |
Correct |
15 ms |
6488 KB |
Output is correct |
| 8 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 9 |
Correct |
27 ms |
12892 KB |
Output is correct |
| 10 |
Correct |
43 ms |
12892 KB |
Output is correct |
| 11 |
Correct |
47 ms |
64080 KB |
Output is correct |
| 12 |
Correct |
179 ms |
178560 KB |
Output is correct |
| 13 |
Incorrect |
122 ms |
163664 KB |
Output isn't correct |
| 14 |
Incorrect |
79 ms |
72056 KB |
Output isn't correct |
| 15 |
Incorrect |
325 ms |
72052 KB |
Output isn't correct |
| 16 |
Incorrect |
149 ms |
186960 KB |
Output isn't correct |
| 17 |
Incorrect |
137 ms |
179964 KB |
Output isn't correct |
| 18 |
Incorrect |
161 ms |
188244 KB |
Output isn't correct |
| 19 |
Incorrect |
220 ms |
188248 KB |
Output isn't correct |
| 20 |
Incorrect |
411 ms |
188200 KB |
Output isn't correct |
