#include <bits/stdc++.h>
using namespace std;
int frec[300005];
int fr[1005][1005],din[1005][1005][21],k,t,z,n,m;
struct wow
{
int x,y;
} v[105];
vector <int> prime;
bool c[300005];
long long lim;
long long ridput (long long a,long long b)
{
if (b==0)
{
return 1;
}
long long rez=ridput(a,b/2);
if (b%2==0)
{
return (rez*rez)%z;
}
return ((rez*rez)%z*a)%z;
}
void adauga(int n,int val)
{
int j;
for (j=0; j<(int)prime.size(); j++)
{
long long p=prime[j];
while (p<=n)
{
frec[prime[j]]+=(n/p)*val;
p=p*prime[j];
}
}
}
long long combinari(int k,int n)
{
int j;
for (j=0; j<(int)prime.size(); j++)
{
frec[prime[j]]=0;
}
adauga(n,1);
adauga(k,-1);
adauga(n-k,-1);
long long p=1;
for (j=0; j<(int)prime.size(); j++)
{
p=(p*ridput(prime[j],frec[prime[j]]))%z;
}
return p;
}
bool dif (int x,int y,int x2,int y2)
{
if (x!=x2||y!=y2)
{
return 1;
}
return 0;
}
bool nimic(int x,int y,int x2,int y2)
{
for (int i=1; i<=k; i++)
{
if (dif(v[i].x,v[i].y,x,y)==1&&dif(v[i].x,v[i].y,x2,y2)==1)
{
if (x<=v[i].x&&v[i].x<=x2&&y<=v[i].y&&v[i].y<=y2)
{
return 0;
}
}
}
return 1;
}
map <pair <int,int> ,long long > mr;
long long nimicpr[105][105];
long long nr(int st,int dr)
{
int x=v[st].x;
int y=v[st].y;
int x2=v[dr].x;
int y2=v[dr].y;
if (x>x2||y>y2)
{
swap(st,dr);
swap(x,x2);
swap(y,y2);
}
long long inc=combinari(x2-x,x2-x+y2-y);
if (nimic(x,y,x2,y2)==1)
{
return combinari(x2-x,x2-x+y2-y);
}
if (mr.find({st,dr})!=mr.end())
{
return mr[{st,dr}];
}
for (int i=1;i<=k;i++)
{
if (dif(v[i].x,v[i].y,x,y)==1&&dif(v[i].x,v[i].y,x2,y2)==1)
{
if (x<=v[i].x&&v[i].x<=x2&&y<=v[i].y&&v[i].y<=y2)
{
inc=(inc-(nr(st,i)*combinari(x2-v[i].x,x2-v[i].x+y2-v[i].y))%z+z)%z;
}
}
}
mr[{st,dr}]=inc;
return inc;
}
long long brut()
{
int i,j;
for (i=1; i<=k; i++)
{
fr[v[i].x][v[i].y]=1;
}
din[1][1][0]=1;
for (i=1; i<=n; i++)
{
for (j=1; j<=m; j++)
{
if (i!=1||j!=1)
{
for (int r=fr[i][j]; r<=k; r++)
{
din[i][j][r]=(din[i][j][r]+din[i-1][j][r-fr[i][j]]+din[i][j-1][r-fr[i][j]])%z;
}
}
}
}
long long sum=0;
for (int r=0; r<=t; r++)
{
sum=(sum+din[n][m][r])%z;
}
return sum;
}
bool compare(int a,int b)
{
return v[a].x<v[b].x||(v[a].x==v[b].x&&v[a].y<v[b].y);
}
long long i,j;
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0);
#ifdef HOME
ifstream cin("turtle.in");
ofstream cout("turtle.out");
#endif // HOME
cin>>n>>m>>k>>t>>z;
n++;
m++;
lim=300000;
c[0]=c[1]=1;
for (i=2; i<=lim; i++)
{
if (c[i]==0)
{
prime.push_back(i);
for (j=i*i; j<=lim; j+=i)
{
c[j]=1;
}
}
}
for (i=1; i<=k; i++)
{
cin>>v[i].x>>v[i].y;
v[i].x++;
v[i].y++;
}
v[0].x=1;
v[0].y=1;
v[k+1].x=n;
v[k+1].y=m;
//cout<<brut()<<'\n';
for (i=0;i<=k+1;i++)
{
for (j=0;j<=k+1;j++)
{
nimicpr[i][j]=nimic(v[i].x,v[i].y,v[j].x,v[j].y);
}
}
lim=(1<<k);
long long sum=nr(0,k+1);
for (int i=1;i<lim;i++)
{
vector <int> sol;
for (int j=0;j<k;j++)
{
if (i&(1<<j))
{
sol.push_back(j+1);
}
}
int ok=1;
sort (sol.begin(),sol.end(),compare);
for (int j=1;j<sol.size();j++)
{
if (v[sol[j-1]].y>v[sol[j]].y)
{
ok=0;
break;
}
}
if (sol.size()>t)
{
ok=0;
}
if (ok==0)
{
continue;
}
long long p=nr(0,sol[0]);
for (int j=1;j<sol.size();j++)
{
p=(p*nr(sol[j-1],sol[j]))%z;
}
int ult=(int)sol.size()-1;
p=(p*nr(sol[ult],k+1))%z;
/*for (j=0;j<sol.size();j++)
{
cout<<sol[j]<<" ";
}
cout<<'\n';
cout<<p<<'\n';*/
sum=(sum+p)%z;
}
cout<<sum;
return 0;
}
Compilation message
turtle.cpp: In function 'int main()':
turtle.cpp:203:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
203 | for (int j=1;j<sol.size();j++)
| ~^~~~~~~~~~~
turtle.cpp:211:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
211 | if (sol.size()>t)
| ~~~~~~~~~~^~
turtle.cpp:220:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
220 | for (int j=1;j<sol.size();j++)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2000 KB |
Output is correct |
| 2 |
Correct |
48 ms |
2012 KB |
Output is correct |
| 3 |
Correct |
31 ms |
2016 KB |
Output is correct |
| 4 |
Correct |
431 ms |
2024 KB |
Output is correct |
| 5 |
Correct |
1593 ms |
2116 KB |
Output is correct |
| 6 |
Execution timed out |
2077 ms |
1996 KB |
Time limit exceeded |
| 7 |
Correct |
767 ms |
2028 KB |
Output is correct |
| 8 |
Correct |
541 ms |
2024 KB |
Output is correct |
| 9 |
Correct |
1392 ms |
2036 KB |
Output is correct |
| 10 |
Correct |
652 ms |
2024 KB |
Output is correct |
| 11 |
Correct |
1266 ms |
2020 KB |
Output is correct |
| 12 |
Execution timed out |
2085 ms |
1996 KB |
Time limit exceeded |
| 13 |
Incorrect |
228 ms |
1996 KB |
Output isn't correct |
| 14 |
Execution timed out |
2075 ms |
1996 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2081 ms |
1996 KB |
Time limit exceeded |
| 16 |
Incorrect |
1605 ms |
2032 KB |
Output isn't correct |
| 17 |
Incorrect |
184 ms |
2024 KB |
Output isn't correct |
| 18 |
Execution timed out |
2088 ms |
1996 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2087 ms |
1996 KB |
Time limit exceeded |
| 20 |
Incorrect |
1414 ms |
2028 KB |
Output isn't correct |
