#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
int n,m,k,t,MOD;
int put(int a, int exp)
{
if(exp==0)
return 1;
if(exp%2==0)
return put((a*a)%MOD,exp/2);
else
return (put((a*a)%MOD,exp/2)*a)%MOD;
}
pair<int,int> traps[25];
int dp[1100000];
int ult[1100000];
int fact[6000015];
int invf[6000015];
int inde;
int comb(int x, int y)
{
return (((((fact[x]*invf[y]%MOD)*invf[x-y])%MOD)));
}
int calc_inde(int x)
{
int d=2;
int prod = x, imp = 1;
while(d*d<=x)
{
if(x%d==0)
{
while(x%d==0)
x/=d;
prod *= d-1;
imp *= d;
}
if(d==2)
d--;
d+=2;
}
if(x>1)
{
prod *= x-1;
imp *= x;
}
return prod/imp;
}
signed main()
{
cin>>n>>m>>k>>t>>MOD;
inde = calc_inde(MOD);
fact[0]=1;
invf[0]=1;
for(int i=1;i<=n+m;i++)
{
fact[i] = (fact[i-1]*i)%MOD;
invf[i] = put(fact[i], inde-1);
}
for(int i=0;i<k;i++)
{
cin>>traps[i].first>>traps[i].second;
}
sort(traps,traps+k);
int rez=comb(n+m,n);
for(int config=1;config<(1<<k);config++)
{
int cnt=0;
for(int i=0;i<k;i++)
if(((1<<i)&config))
cnt++;
for(int i=0;i<k;i++)
{
if(((1<<i)&config) && (cnt==1 || (traps[ult[config-(1<<i)]].first <= traps[i].first && traps[ult[config-(1<<i)]].second <= traps[i].second)))
{
ult[config]=i;
if(cnt>1)
{
int j = ult[config-(1<<i)];
dp[config] = (dp[config-(1<<i)] * comb((traps[i].first - traps[j].first) + (traps[i].second - traps[j].second), (traps[i].second - traps[j].second)))%MOD;
}
else
dp[config] = comb(traps[i].first + traps[i].second, traps[i].first);
//cout<<config<<" "<<dp[config]<<" "<<comb(n - traps[i].first + m - traps[i].second, n - traps[i].first)<<" zzz\n";
if(cnt>t)
{
rez = rez + MOD - (dp[config] * comb(n - traps[i].first + m - traps[i].second, n - traps[i].first))%MOD;
rez%=MOD;
for(int config2=0;config2<(1<<cnt)-1;config2++)
{
int cnt2=0;
for(int u=0;u<cnt;u++)
if((((1<<u)&config2)))
cnt2++;
if(cnt2>t)
rez = (rez + (dp[config] * comb(n - traps[i].first + m - traps[i].second, n - traps[i].first))%MOD)%MOD;
}
rez%=MOD;
}
break;
}
}
}
cout<<rez;
return 0;
}
/**
1 4 2 1 100000
0 3
1 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 3 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
55 ms |
8628 KB |
Output is correct |
| 5 |
Correct |
83 ms |
21068 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 7 |
Correct |
73 ms |
8540 KB |
Output is correct |
| 8 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 9 |
Execution timed out |
2089 ms |
10760 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2080 ms |
10836 KB |
Time limit exceeded |
| 11 |
Correct |
112 ms |
13164 KB |
Output is correct |
| 12 |
Execution timed out |
2064 ms |
22256 KB |
Time limit exceeded |
| 13 |
Incorrect |
112 ms |
14952 KB |
Output isn't correct |
| 14 |
Incorrect |
676 ms |
14968 KB |
Output isn't correct |
| 15 |
Incorrect |
148 ms |
25220 KB |
Output isn't correct |
| 16 |
Execution timed out |
2032 ms |
21072 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2003 ms |
21072 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2025 ms |
23392 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2074 ms |
23168 KB |
Time limit exceeded |
| 20 |
Incorrect |
456 ms |
33416 KB |
Output isn't correct |
