#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAX_K = 22;
const ll MAX_N = 3e5+2;
ll MOD=1e9+7;
ll dp1[MAX_K][MAX_K]; /// i1 -> i2 kato stupvash na i2 i produljavash
ll dp2[MAX_K][MAX_K]; /// i1 -> i2, kato sled i2 nqma drugi kapani
ll dist[MAX_K][MAX_K];
ll n,m,k,t;
ll primes[MAX_N],primes_br = 0,vis[MAX_N];
pair<ll,ll> traps[MAX_K];
void sieve()
{
for(ll i=2; i<=MAX_N; i++)
{
if(vis[i]) continue;
primes[primes_br] = i; primes_br++;
for(ll j=2*i; j<=MAX_N; j+=i) vis[j] = true;
}
}
ll find_power(ll num, ll p)
{
ll res = 0;
while(num > 0)
{
num/=p;
res+=num;
}
return res;
}
ll fast_pow(ll num, ll st)
{
if(st == 0) return 1;
ll temp = fast_pow(num,st/2);
if(st&1) return ((((temp*temp)%MOD)*num)%MOD);
return ((temp*temp)%MOD);
}
ll combi(ll k, ll n)
{
ll res = 1;
for(ll i=0; primes[i]<=n; i++)
{
ll pw = find_power(n,primes[i])-find_power(k,primes[i])-find_power(n-k,primes[i]);
res *= fast_pow(primes[i],pw);
res %= MOD;
}
return res;
}
ll no_traps(ll start_idx, ll end_idx)
{
if(dp2[start_idx][end_idx]) return dp2[start_idx][end_idx];
ll res = dist[start_idx][end_idx];
for(ll middle_idx=start_idx+1; middle_idx<=end_idx-1; middle_idx++)
{
if(traps[start_idx].second <= traps[middle_idx].second && traps[middle_idx].second <= traps[end_idx].second)
{
res -= (no_traps(start_idx,middle_idx)*dist[middle_idx][end_idx])%MOD;
while(res < 0) res += MOD;
res %= MOD;
}
}
dp2[start_idx][end_idx] = res;
return res;
}
ll rec(ll idx, ll stepped_traps)
{
if(idx == k+1) return 1;
if(stepped_traps > t) return 0;
if(dp1[idx][stepped_traps]) return dp1[idx][stepped_traps];
ll res = 0;
for(ll next_idx = idx+1; next_idx <= k+1; next_idx++)
{
if(traps[idx].second <= traps[next_idx].second)
{
res += (no_traps(idx,next_idx)*rec(next_idx,stepped_traps+1))%MOD;
res %= MOD;
}
}
dp1[idx][stepped_traps] = res;
return res;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
sieve();
cin>>n>>m>>k>>t>>MOD;
traps[0] = {0,0};
ll x1,y1;
for(ll i=1; i<=k; i++)
{
cin>>x1>>y1;
traps[i] = {x1,y1};
}
traps[k+1] = {n,m};
sort(traps,traps+k+1);
for(ll i=0; i<=k+1; i++)
{
for(ll j=i+1; j<=k+1; j++)
{
if(traps[i].second <= traps[j].second)
{
dist[i][j] = combi(traps[j].first-traps[i].first,traps[j].first-traps[i].first+traps[j].second-traps[i].second);
}
}
}
cout<<rec(0,0)<<endl;
}
/**
4 4 2 1 1000000007
1 1
2 2
*/
Compilation message
turtle.cpp: In function 'void sieve()':
turtle.cpp:17:17: warning: iteration 300000 invokes undefined behavior [-Waggressive-loop-optimizations]
17 | if(vis[i]) continue;
| ~~~~~^
turtle.cpp:15:18: note: within this loop
15 | for(ll i=2; i<=MAX_N; i++)
| ~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2764 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2764 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2764 KB |
Output is correct |
| 9 |
Correct |
5 ms |
2764 KB |
Output is correct |
| 10 |
Correct |
6 ms |
2764 KB |
Output is correct |
| 11 |
Correct |
20 ms |
2876 KB |
Output is correct |
| 12 |
Runtime error |
8 ms |
5564 KB |
Execution killed with signal 8 |
| 13 |
Runtime error |
7 ms |
5564 KB |
Execution killed with signal 8 |
| 14 |
Correct |
26 ms |
2876 KB |
Output is correct |
| 15 |
Correct |
28 ms |
2764 KB |
Output is correct |
| 16 |
Runtime error |
8 ms |
5584 KB |
Execution killed with signal 8 |
| 17 |
Runtime error |
8 ms |
5580 KB |
Execution killed with signal 8 |
| 18 |
Runtime error |
8 ms |
5580 KB |
Execution killed with signal 8 |
| 19 |
Runtime error |
8 ms |
5580 KB |
Execution killed with signal 8 |
| 20 |
Runtime error |
8 ms |
5596 KB |
Execution killed with signal 8 |
