#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) {
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 power(long long int x, long long int j) {
long long int h = vv[j] / v[j].first * (v[j].first - 1);
h--;
return power(x, h, vv[j]);
}
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], 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], 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:26: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]
26 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
turtle.cpp:35: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]
35 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
turtle.cpp: In function 'int main()':
turtle.cpp:78: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]
78 | for (int j = 0; j < v.size(); j++) {
| ~~^~~~~~~~~~
turtle.cpp:91: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]
91 | for (int j = 0; j < v.size(); j++) {
| ~~^~~~~~~~~~
turtle.cpp:135:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for (int i = 1; i < v.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6648 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
9 ms |
6488 KB |
Output is correct |
| 5 |
Correct |
262 ms |
6628 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
16 ms |
6724 KB |
Output is correct |
| 8 |
Correct |
1 ms |
6744 KB |
Output is correct |
| 9 |
Correct |
27 ms |
12952 KB |
Output is correct |
| 10 |
Correct |
43 ms |
12892 KB |
Output is correct |
| 11 |
Correct |
47 ms |
64080 KB |
Output is correct |
| 12 |
Correct |
181 ms |
178564 KB |
Output is correct |
| 13 |
Correct |
125 ms |
163728 KB |
Output is correct |
| 14 |
Correct |
78 ms |
72016 KB |
Output is correct |
| 15 |
Correct |
312 ms |
72276 KB |
Output is correct |
| 16 |
Correct |
152 ms |
186896 KB |
Output is correct |
| 17 |
Correct |
142 ms |
179932 KB |
Output is correct |
| 18 |
Correct |
168 ms |
188148 KB |
Output is correct |
| 19 |
Correct |
220 ms |
188244 KB |
Output is correct |
| 20 |
Correct |
421 ms |
188312 KB |
Output is correct |
