#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 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(dp[pos][i]*1LL*rec(i,turn+1)));
return ret;
}
int mm[11][11][22],ban[11][11];
int solve(int x,int y,int turn){
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+=solve(x+1,y,turn+ban[x+1][y]);
if(y+1<=m)
ret+=solve(x,y+1,turn+ban[x][y+1]);
ret%=MOD;
return ret;
}
int main(){
//~ freopen("file.in", "r", stdin);
scanf("%d%d%d%d%d",&n,&m,&k,&t,&MOD);
if(n<=10 and m<=10){
while(k--){
int x,y;
scanf("%d%d",&x,&y);
ban[x][y]=1;
}
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;
}
for(int i=1;i<=k;i++){
int x,y;
scanf("%d%d",&x,&y);
arr[i]=mp(x,y);
}
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(memo,-1,sizeof memo);
printf("%d\n",rec(0,0));
return 0;
}
Compilation message
turtle.cpp: In function 'int rec(int, int)':
turtle.cpp:64:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(~ret)
^~
turtle.cpp:65: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:76:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(~ret)
^~
turtle.cpp:77: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:87: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:91:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
~~~~~^~~~~~~~~~~~~~
turtle.cpp:107: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 |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
252 KB |
Output is correct |
| 3 |
Correct |
4 ms |
760 KB |
Output is correct |
| 4 |
Correct |
5 ms |
760 KB |
Output is correct |
| 5 |
Correct |
5 ms |
760 KB |
Output is correct |
| 6 |
Correct |
6 ms |
732 KB |
Output is correct |
| 7 |
Correct |
6 ms |
760 KB |
Output is correct |
| 8 |
Correct |
6 ms |
760 KB |
Output is correct |
| 9 |
Correct |
18 ms |
760 KB |
Output is correct |
| 10 |
Correct |
23 ms |
760 KB |
Output is correct |
| 11 |
Correct |
85 ms |
764 KB |
Output is correct |
| 12 |
Incorrect |
136 ms |
764 KB |
Output isn't correct |
| 13 |
Incorrect |
59 ms |
760 KB |
Output isn't correct |
| 14 |
Correct |
183 ms |
772 KB |
Output is correct |
| 15 |
Correct |
153 ms |
760 KB |
Output is correct |
| 16 |
Incorrect |
140 ms |
768 KB |
Output isn't correct |
| 17 |
Incorrect |
125 ms |
760 KB |
Output isn't correct |
| 18 |
Incorrect |
315 ms |
780 KB |
Output isn't correct |
| 19 |
Incorrect |
274 ms |
764 KB |
Output isn't correct |
| 20 |
Incorrect |
112 ms |
768 KB |
Output isn't correct |
