#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define foreach(it, S) for (__typeof (S.begin()) it = S.begin(); it != S.end(); it++)
#define all(x) x.begin(), x.end()
#define endl '\n'
#define _ ios_base :: sync_with_stdio(false); cin.tie(NULL);
#ifdef inputf
#define fname ""
#else
#define fname "" // <- Here
#endif
const double eps = 1e-9;
const int MaxN = int(2e5) + 256;
const int MOD = int(1e9) + 7;
template <typename T> inline T gcd(T a, T b) {
return b ? gcd (b, a % b) : a;
}
inline bool Palindrome(const string& s) {
return equal(s.begin(), s.end(), s.rbegin());
}
int d[21][1200][1200];
int f[10 * MaxN], inv[10 * MaxN];
int a[1200][1200];
int c[5000][5000];
inline int binpow(int a, int n, int z) {
int res = 1;
while (n) {
if (n & 1)
res = (res * 1ll * a) % z;
a = (a * 1ll * a) % z;
n >>= 1;
}
return res;
}
inline int get(int n, int k, int z) {
return f[n] * inv[k] % z * inv[n - k] % z;
}
inline bool prime(int v) {
for (int i = 2; i * i <= v; ++i)
if (v % i == 0)
return false;
return true;
}
int n, m, k, t, z;
int q(int cnt, int x, int y) {
if (cnt > t || x > n || y > m)
return 0;
if (x == n && y == m)
return 1;
int &res = d[cnt][x][y];
if (~res)
return res;
res = 0;
if (a[x][y])
++cnt;
res = (q(cnt, x + 1, y) + q(cnt, x, y + 1)) % z;
return res;
}
int main() { // _
#ifdef lcl
freopen(fname".in", "r", stdin);
freopen(fname".out", "w", stdout);
#endif
scanf("%d%d%d%d%d", &n, &m, &k, &t, &z);
for (int i = 0; i < k; ++i) {
int x, y; scanf("%d%d", &x, &y);
a[x][y] = 1;
}
f[0] = inv[0] = 1;
for (int i = 1; i <= n + m; ++i) {
f[i] = f[i - 1] * 1ll * i % z;
inv[i] = binpow(f[i], z - 2, z);
}
if (!k) {
cout << get(n + m, n, z);
return 0;
}
memset(d, 255, sizeof d);
cout << q(0, 0, 0);
return 0;
}
Compilation message
turtle.cpp: In function 'int main()':
turtle.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d%d", &n, &m, &k, &t, &z);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
turtle.cpp:82:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x, y; scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
124 ms |
118684 KB |
Output is correct |
| 3 |
Correct |
102 ms |
118648 KB |
Output is correct |
| 4 |
Correct |
106 ms |
118748 KB |
Output is correct |
| 5 |
Correct |
105 ms |
118780 KB |
Output is correct |
| 6 |
Correct |
136 ms |
118780 KB |
Output is correct |
| 7 |
Correct |
132 ms |
119032 KB |
Output is correct |
| 8 |
Correct |
162 ms |
118904 KB |
Output is correct |
| 9 |
Incorrect |
196 ms |
119160 KB |
Output isn't correct |
| 10 |
Incorrect |
161 ms |
119204 KB |
Output isn't correct |
| 11 |
Runtime error |
13 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Incorrect |
468 ms |
123816 KB |
Output isn't correct |
| 13 |
Runtime error |
15 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Incorrect |
407 ms |
120836 KB |
Output isn't correct |
| 15 |
Runtime error |
14 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
14 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
14 ms |
376 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
15 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Incorrect |
696 ms |
123896 KB |
Output isn't correct |
| 20 |
Runtime error |
16 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
