#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
const int SZ = 300005, K_ = 30;
int N, M, K, T, Z;
vector<int> primes;
bool sieve[SZ+SZ];
void getPrimes (int MX) {
for(int p = 2; p <= MX; p++) {
if(sieve[p]) continue;
primes.push_back(p);
for(int x = p+p; x <= MX; x += p) sieve[x] = true;
}
}
ll power (ll a, ll b) {
ll ret = 1;
while(b > 0) {
if(b & 1) ret = (ret * a) % Z;
a = (a * a) % Z;
b >>= 1;
}
return ret;
}
int nCr (int n, int r) {
if(r == 0 || n == r) return 1;
if(r == 1 || r == n-1) return n;
ll ret = 1;
for(int x = 0; x < primes.size(); x++) {
int p = primes[x];
if(p > n) break;
ll v = 0;
for(ll w = p; w <= n; w *= p) v += n / w;
for(ll w = p; w <= r; w *= p) v -= r / w;
for(ll w = p; w <= n-r; w *= p) v -= (n-r) / w;
ret *= power(p, v);
ret %= Z;
}
return ret % Z;
}
int ways (int x, int y) { // (x+y) C x
return nCr (x+y, x);
}
struct point {
int x, y;
point(int x = 0, int y = 0): x(x), y(y) { }
bool operator< (const point &p) const { return x != p.x ? x < p.x : y < p.y; }
} D[K_];
int F[K_], R[K_];
int W[K_][K_];
int Table[1<<20];
int LB[1<<20], CB[1<<20];
int Sum[K_];
ll res;
int main() {
int i, j, k;
scanf("%d%d%d%d%d", &N, &M, &K, &T, &Z);
for(i = 0; i < K; i++) scanf("%d%d", &D[i].x, &D[i].y);
if(K == 0) return 0 & printf("%d\n", ways(N, M));
getPrimes(N+M);
sort(D, D+K);
for(i = 0; i < K; i++) {
F[i] = ways(D[i].x, D[i].y);
R[i] = ways(N - D[i].x, M - D[i].y);
for(j = i+1; j < K; j++) {
if(D[j].y >= D[i].y) W[i][j] = ways(D[j].x - D[i].x, D[j].y - D[i].y);
}
}
Table[0] = 1;
for(i = 0; i < K; i++) {
Table[1<<i] = F[i];
LB[1<<i] = i;
CB[1<<i] = 1;
for(int prev = 1; prev < (1<<i); prev++) {
int now = prev | (1<<i);
Table[now] = ((ll)Table[prev] * W[LB[prev]][i]) % Z;
LB[now] = i;
CB[now] = CB[prev] + 1;
}
}
Table[0] = Sum[0] = ways(N, M);
for(i = 1; i < (1<<K); i++) {
Sum[CB[i]] += ((ll)Table[i] * R[LB[i]]) % Z;
if(Sum[CB[i]] >= Z) Sum[CB[i]] -= Z;
}
for(k = 0; k <= T; k++) {
int s = 1;
for(i = k; i <= K; i++) {
res += s * (((ll)Sum[i] * nCr(i, k)) % Z);
if(res < 0) res += Z;
res %= Z;
s = -s;
}
}
printf("%lld\n", res);
return 0;
}
Compilation message
turtle.cpp: In function 'int nCr(int, int)':
turtle.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int x = 0; x < primes.size(); x++) {
| ~~^~~~~~~~~~~~~~~
turtle.cpp: In function 'int main()':
turtle.cpp:95:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | scanf("%d%d%d%d%d", &N, &M, &K, &T, &Z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
turtle.cpp:96:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | for(i = 0; i < K; i++) scanf("%d%d", &D[i].x, &D[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
11 ms |
12632 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4700 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
5 ms |
11740 KB |
Output is correct |
| 10 |
Correct |
8 ms |
11612 KB |
Output is correct |
| 11 |
Correct |
13 ms |
4952 KB |
Output is correct |
| 12 |
Correct |
36 ms |
12616 KB |
Output is correct |
| 13 |
Correct |
15 ms |
5336 KB |
Output is correct |
| 14 |
Correct |
18 ms |
5456 KB |
Output is correct |
| 15 |
Correct |
27 ms |
12884 KB |
Output is correct |
| 16 |
Correct |
40 ms |
13516 KB |
Output is correct |
| 17 |
Correct |
30 ms |
12496 KB |
Output is correct |
| 18 |
Correct |
49 ms |
13632 KB |
Output is correct |
| 19 |
Correct |
46 ms |
13444 KB |
Output is correct |
| 20 |
Correct |
40 ms |
13636 KB |
Output is correct |
