#include "bits/stdc++.h"
using namespace std;
#define fast_io() ios::sync_with_stdio(false)
#define int long long
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define snd second
#define fst first
#define pb push_back
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
const int NMAX = 300100;
int N, M, K, T, Z;
vi primes;
vii traps;
vi adj[30];
int mod(int n){
if(n >= 0) return n % Z;
else return (n%Z) + Z;
}
int expcnt(int n, int p){
int res = 0;
while(n){
n/= p;
res += n;
}
return res;
}
int mpow(int a, int b){
if(b == 0) return 1;
if(b & 1) return a*mpow(a*a%Z, b>>1)%Z;
return mpow(a*a%Z, b>>1);
}
int C(int a, int b){
// a! / (b!(a-b)!)
int res = 1;
for(int i = 0; primes[i] <= a; i++){
int ex = expcnt(a, primes[i]) - expcnt(b, primes[i]) - expcnt(a-b, primes[i]);
res = mod(res * mpow(primes[i], ex));
}
return res;
}
int dp3[30][30];
int ways(int a, int b){
int &res = dp3[a][b];
if(res != -1) return res;
int dx = traps[a].fst - traps[b].fst, dy = traps[a].snd - traps[b].snd;
if(dx < 0 or dy < 0) return res = 0;
return res = C(dx + dy, dx);
}
int dp1[30][30];
// paths from trap a to b passing through no other traps
// a > b
int numPaths(int a, int b){
int &res = dp1[a][b];
if(res != -1) return res;
if(traps[a].fst - traps[b].fst < 0 or traps[a].snd - traps[b].snd < 0) return res = 0;
res = ways(a, b);
//cout << a << " " << b << endl;
//cout << "sres " <<res <<endl;
for(int t : adj[a]) if(t!=b){
int o = mod(ways(a, t) * numPaths(t, b));
//cout << a << " " << t << " " << b << endl;
//cout << "o " << o << " " << ways(traps[a].fst - traps[t].fst, traps[a].snd - traps[t].snd) << " " << numPaths(t, b) << endl;
res -= o;
}
//cout << "res " << res << endl;
res = mod(res);
return res;
}
int dp2[30][100];
// from trap a to 0, 0 through at least t traps
int f(int a, int t){
//cout << a << " " << t << endl;
int &res = dp2[a][t+30];
if(res != -1) return res;
if(a == 0){
return res = (t < 0);
}
res = 0;
for(int k : adj[a]){
res = mod(res + f(k, t-1) * numPaths(a, k) );
}
return res;
}
signed main(){
FOR(i, 0, 30) FOR(j, 0, 30) dp1[i][j] = -1;
FOR(i, 0, 30) FOR(j, 0, 100) dp2[i][j] = -1;
FOR(i, 0, 30) FOR(j, 0, 30) dp3[i][j] = -1;
fast_io();
cin >> N >> M >> K >> T >> Z;
bitset<NMAX*4> isPrime;
isPrime.set();
isPrime[0] = isPrime[1] = 0;
for(int i = 0; i*i < NMAX*4; i++){
if(isPrime[i])
for(int j = 2*i; j < NMAX*4; j += i){
isPrime[j] = 0;
}
}
FOR(i, 0, NMAX*4) if(isPrime[i]) primes.pb(i);
//cout << C(5, 2) << endl;
traps.pb({0, 0});
FOR(i, 0, K) {
int x, y;
cin >> x >> y;
traps.pb({x, y});
}
traps.pb({N, M});
FOR(i, 0, traps.size()) FOR(j, 0, traps.size()){
if(i != j and traps[i].fst <= traps[j].fst and traps[i].snd <= traps[j].snd){
adj[j].pb(i);
}
}
/*
FOR(i, 0, traps.size()) {
FOR(j, 0, traps.size()){
numPaths(i, j);
//cout << << " ";
}
//cout << endl;
}
FOR(i, 0, traps.size()) {
FOR(j, 0, traps.size()){
cout << numPaths(i, j) << " ";
}
cout << endl;
}
*/
//cout << f( (int) traps.size()-1, 0) << endl;
cout << mod(ways(K+1, 0) - f( (int) traps.size()-1, T+1) ) << endl;
}
/*
300000 300000 20 10 1000000007
18467 41
26500 6334
15724 19169
29358 11478
24464 26962
28145 5705
16827 23281
491 9961
11942 2995
5436 4827
14604 32391
153 3902
12382 292
18716 17421
19895 19718
21726 5447
11538 14771
19912 1869
26299 25667
9894 17035
*/
Compilation message
turtle.cpp: In function 'int main()':
turtle.cpp:6:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
^
turtle.cpp:129:5: note: in expansion of macro 'FOR'
FOR(i, 0, traps.size()) FOR(j, 0, traps.size()){
^~~
turtle.cpp:6:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
^
turtle.cpp:129:29: note: in expansion of macro 'FOR'
FOR(i, 0, traps.size()) FOR(j, 0, traps.size()){
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
1652 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1652 KB |
Output is correct |
| 3 |
Correct |
14 ms |
1624 KB |
Output is correct |
| 4 |
Correct |
14 ms |
1656 KB |
Output is correct |
| 5 |
Correct |
14 ms |
1652 KB |
Output is correct |
| 6 |
Correct |
14 ms |
1652 KB |
Output is correct |
| 7 |
Correct |
15 ms |
1648 KB |
Output is correct |
| 8 |
Correct |
14 ms |
1652 KB |
Output is correct |
| 9 |
Correct |
20 ms |
1712 KB |
Output is correct |
| 10 |
Correct |
22 ms |
1652 KB |
Output is correct |
| 11 |
Correct |
59 ms |
1708 KB |
Output is correct |
| 12 |
Correct |
129 ms |
1652 KB |
Output is correct |
| 13 |
Correct |
67 ms |
1648 KB |
Output is correct |
| 14 |
Correct |
76 ms |
1652 KB |
Output is correct |
| 15 |
Correct |
83 ms |
1652 KB |
Output is correct |
| 16 |
Correct |
147 ms |
1652 KB |
Output is correct |
| 17 |
Correct |
125 ms |
1652 KB |
Output is correct |
| 18 |
Correct |
159 ms |
1780 KB |
Output is correct |
| 19 |
Correct |
160 ms |
1652 KB |
Output is correct |
| 20 |
Correct |
129 ms |
1652 KB |
Output is correct |
