#include <bits/stdc++.h>
using namespace std;
int n,m,k,t,mod;
int dp[25][25];
int val[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;
int tmpp = l/u;
if(l != tmpp*u)tmpp++;
cnt += (r/u - tmpp) + 1;
l = 1, r = y;
cnt -= r/u;
if(1ll*u*tmp > x)break;
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++){
for(int j=0;j<i;j++){
if(v[j].second <= v[i].second)
val[i][j] = nCr(v[i].first - v[j].first + v[i].second - v[j].second,v[i].first - v[j].first);
}
}
for(int i=1;i<v.size();i++){
int sum = 0;
for(int x = k;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)]*val[i][j])%mod;
}
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:72: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]
72 | for(int i=1;i<v.size();i++){
| ~^~~~~~~~~
turtle.cpp:74:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int x = k;x>=1 - (i == v.size()-1);x--){
| ~~^~~~~~~~~~~~~
turtle.cpp:78: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]
78 | dp[i][x] = (dp[i][x] + 1ll*dp[j][x-(i != v.size() - 1)]*val[i][j])%mod;
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
3020 KB |
Output is correct |
| 2 |
Correct |
13 ms |
3008 KB |
Output is correct |
| 3 |
Correct |
12 ms |
3020 KB |
Output is correct |
| 4 |
Correct |
13 ms |
3020 KB |
Output is correct |
| 5 |
Correct |
13 ms |
3036 KB |
Output is correct |
| 6 |
Correct |
13 ms |
3000 KB |
Output is correct |
| 7 |
Correct |
13 ms |
3020 KB |
Output is correct |
| 8 |
Correct |
13 ms |
3020 KB |
Output is correct |
| 9 |
Correct |
15 ms |
3040 KB |
Output is correct |
| 10 |
Correct |
16 ms |
3020 KB |
Output is correct |
| 11 |
Correct |
29 ms |
3020 KB |
Output is correct |
| 12 |
Correct |
53 ms |
3020 KB |
Output is correct |
| 13 |
Correct |
31 ms |
3020 KB |
Output is correct |
| 14 |
Correct |
32 ms |
3052 KB |
Output is correct |
| 15 |
Correct |
35 ms |
3020 KB |
Output is correct |
| 16 |
Correct |
52 ms |
3020 KB |
Output is correct |
| 17 |
Correct |
51 ms |
3044 KB |
Output is correct |
| 18 |
Correct |
64 ms |
3020 KB |
Output is correct |
| 19 |
Correct |
61 ms |
3020 KB |
Output is correct |
| 20 |
Correct |
51 ms |
3020 KB |
Output is correct |
