#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x) cerr<< #x <<" = "<< x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int K=22,N=3e5+5;
PII arr[K];
int dis[K][K],dp[K][K],memo[K][K];
bool vis[N];
int prime[N],c,n,m,k,t,MOD;
int mod(ll x){
while(x<0)
x+=MOD;
return (x%MOD);
}
int Fe(int x,int y){
if(!y)
return 1;
int h=Fe(x,y/2);
h=mod(h*1LL*h);
if(y&1)
h=mod(h*1LL*x);
return h;
}
int cnt(int x,int p){
int res=0;
while(x){
x/=p;
res+=x;
}
return res;
}
int C(int x,int y){
int ans=1;
for(int i=0;prime[i]<=x and i<c;i++){
int pw=cnt(x,prime[i])-cnt(y,prime[i])-cnt(x-y,prime[i]);
ans=mod(ans*1LL*Fe(prime[i],pw));
}
return ans;
}
int way(int x,int y){
return C(x+y-2,x-1);
}
int dynamic(int l,int r){
int &ret=dp[l][r];
if(~ret)
return ret;
ret=dis[l][r];
for(int mid=l+1;mid<r;mid++)
if(arr[mid].ss>=arr[l].ss and arr[r].ss>=arr[mid].ss)
ret=mod(ret-mod(dynamic(l,mid)*1LL*dis[mid][r]));
return ret;
}
int rec(int pos,int turn){
if(pos==k+1)
return 1;
if(turn>t)
return 0;
int &ret=memo[pos][turn];
if(~ret)
return ret;ret=0;
for(int i=pos+1;i<=k+1;i++)
if(arr[i].ss>=arr[pos].ss)
ret=mod(ret+mod(dynamic(pos,i)*1LL*rec(i,turn+1)));
return ret;
}
int mm[1005][1005][22],ban[1005][1005];
int solve(int x,int y,int turn){
if(turn>t)
return 0;
if(x==n and y==m)
return (turn<=t);
int &ret=mm[x][y][turn];
if(~ret)
return ret;ret=0;
if(x+1<=n)
ret=mod(ret+solve(x+1,y,turn+ban[x+1][y]));
if(y+1<=m)
ret=mod(ret+solve(x,y+1,turn+ban[x][y+1]));
return ret;
}
int main(){
//~ freopen("file.in", "r", stdin);
scanf("%d%d%d%d%d",&n,&m,&k,&t,&MOD);
for(int i=1;i<=k;i++){
int x,y;
scanf("%d%d",&x,&y);
arr[i]=mp(x,y);
if(n<=1000 and m<=1000)
ban[x][y]=1;
}
if(n<=1000 and m<=1000){
memset(mm,-1,sizeof mm);
printf("%d\n",solve(0,0,0));
return 0;
}
for(int i=2;i<N;i++){
if(vis[i])
continue;
for(int j=i;j<N;j+=i)
vis[j]=1;
prime[c++]=i;
}
arr[0]=mp(0,0);
arr[k+1]=mp(n,m);
sort(arr,arr+k+2);
for(int i=0;i<=k;i++)
for(int j=i+1;j<=k+1;j++)
if(arr[j].ss>=arr[i].ss)
dis[i][j]=way(arr[j].ff-arr[i].ff+1,arr[j].ss-arr[i].ss+1);
//~ for(int h=k+1;h>=1;h--)
//~ for(int i=h-1;i>=0;i--)
//~ if(arr[i].ss<=arr[h].ss){
//~ dp[i][h]=way(arr[h].ff-arr[i].ff+1,arr[h].ss-arr[i].ss+1);
//~ printf("way(%d)(%d) = %d\n",i,h,way(arr[h].ff-arr[i].ff+1,arr[h].ss-arr[i].ss+1));
//~ for(int j=i+1;j<h;j++)
//~ if(arr[j].ss>=arr[i].ss and arr[h].ss>=arr[j].ss)
//~ dp[i][h]=mod(dp[i][h]-mod(dp[j][h]*1LL*way(arr[j].ff-arr[i].ff+1,arr[j].ss-arr[i].ff+1)));
//~ }
//~ for(int i=0;i<=k;i++)
//~ for(int j=i+1;j<=k+1;j++)
//~ printf("dp[%d][%d] = %d\n",i,j,dp[i][j]);
memset(dp,-1,sizeof dp);memset(memo,-1,sizeof memo);
printf("%d\n",rec(0,0));
return 0;
}
Compilation message
turtle.cpp: In function 'int rec(int, int)':
turtle.cpp:74:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(~ret)
^~
turtle.cpp:75:14: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
return ret;ret=0;
^~~
turtle.cpp: In function 'int solve(int, int, int)':
turtle.cpp:88:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(~ret)
^~
turtle.cpp:89:14: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
return ret;ret=0;
^~~
turtle.cpp: In function 'int main()':
turtle.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d%d",&n,&m,&k,&t,&MOD);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
turtle.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
87288 KB |
Output is correct |
| 2 |
Correct |
75 ms |
87256 KB |
Output is correct |
| 3 |
Correct |
83 ms |
87320 KB |
Output is correct |
| 4 |
Correct |
76 ms |
87388 KB |
Output is correct |
| 5 |
Correct |
80 ms |
87388 KB |
Output is correct |
| 6 |
Correct |
126 ms |
87488 KB |
Output is correct |
| 7 |
Correct |
135 ms |
87416 KB |
Output is correct |
| 8 |
Correct |
209 ms |
87612 KB |
Output is correct |
| 9 |
Correct |
7 ms |
760 KB |
Output is correct |
| 10 |
Correct |
9 ms |
760 KB |
Output is correct |
| 11 |
Correct |
30 ms |
760 KB |
Output is correct |
| 12 |
Incorrect |
44 ms |
760 KB |
Output isn't correct |
| 13 |
Incorrect |
25 ms |
760 KB |
Output isn't correct |
| 14 |
Correct |
40 ms |
760 KB |
Output is correct |
| 15 |
Correct |
44 ms |
772 KB |
Output is correct |
| 16 |
Incorrect |
49 ms |
776 KB |
Output isn't correct |
| 17 |
Incorrect |
43 ms |
764 KB |
Output isn't correct |
| 18 |
Incorrect |
65 ms |
736 KB |
Output isn't correct |
| 19 |
Incorrect |
52 ms |
772 KB |
Output isn't correct |
| 20 |
Incorrect |
36 ms |
760 KB |
Output isn't correct |
