#include <bits/stdc++.h>
using namespace std;
int n,m,k,t,mod;
int dp[25][25];
int vis[600005];
vector<int> p;
int binpow(int a,int b){
int ret = 1;
while(b){
if(b&1){
ret = 1ll*ret * a%mod;
}
a = 1ll*a*a%mod;
b >>= 1;
}
return ret;
}
int nCr(int x,int y){
y = min(y,x-y);
int ret = 1;
for(auto u:p){
int cnt = 0;
int tmp = u;
if(u > x)break;
while(u <= x){
int l = x - y+1,r = x;
l = (l + (u - l%u)%u);
r = (r - (r % u));
cnt += (r - l)/u + 1;
l = 1, r = y;
l = (l + (u - l%u)%u);
r = (r - (r % u));
cnt -= (r - l)/u + 1;
u *= tmp;
}
ret = 1ll*ret * binpow(tmp,cnt)%mod;
}
return ret;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
for(int i=2;i<600005;i++){
if(!vis[i]){
p.push_back(i);
for(int j=2*i;j<600005;j+=i){
vis[j]=1;
}
}
}
cin >> n >> m >> k >> t >> mod;
vector<pair<int,int>> v;
for(int i=0;i<k;i++){
int x,y;
cin >> x >> y;
v.push_back({x,y});
}
v.push_back({0,0});
v.push_back({n,m});
sort(v.begin(),v.end());
dp[0][0] = 1;
for(int i=1;i<v.size();i++){
//cout << v[i].first << " " << v[i].second << endl;
int sum = 0;
for(int x = t+1;x>=1 - (i == v.size()-1);x--){
dp[i][x] = (mod - sum) % mod;
for(int j=0;j<i;j++){
if(v[j].second <= v[i].second)
dp[i][x] = (dp[i][x] + 1ll*dp[j][x-(i != v.size() - 1)]*nCr(v[i].first - v[j].first + v[i].second - v[j].second,v[i].first - v[j].first))%mod;
}
//cout << dp[i][x] <<endl;
sum = (sum + dp[i][x])%mod;
}
}
int ans = 0;
for(int i=0;i<=t;i++){
ans = (ans + dp[v.size()-1][i])%mod;
}
cout << ans;
}
Compilation message
turtle.cpp: In function 'int main()':
turtle.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(int i=1;i<v.size();i++){
| ~^~~~~~~~~
turtle.cpp:69:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int x = t+1;x>=1 - (i == v.size()-1);x--){
| ~~^~~~~~~~~~~~~
turtle.cpp:73:59: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | dp[i][x] = (dp[i][x] + 1ll*dp[j][x-(i != v.size() - 1)]*nCr(v[i].first - v[j].first + v[i].second - v[j].second,v[i].first - v[j].first))%mod;
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
3020 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
3020 KB |
Output isn't correct |
| 3 |
Correct |
13 ms |
3032 KB |
Output is correct |
| 4 |
Correct |
15 ms |
3032 KB |
Output is correct |
| 5 |
Correct |
22 ms |
3020 KB |
Output is correct |
| 6 |
Incorrect |
15 ms |
3040 KB |
Output isn't correct |
| 7 |
Correct |
20 ms |
3020 KB |
Output is correct |
| 8 |
Correct |
17 ms |
3020 KB |
Output is correct |
| 9 |
Correct |
45 ms |
3052 KB |
Output is correct |
| 10 |
Correct |
63 ms |
3020 KB |
Output is correct |
| 11 |
Execution timed out |
2098 ms |
2976 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2087 ms |
3020 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2090 ms |
3020 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2083 ms |
3020 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2096 ms |
3020 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2057 ms |
3020 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2098 ms |
3020 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2089 ms |
3004 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2090 ms |
3020 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2090 ms |
3020 KB |
Time limit exceeded |
