#include <bits/stdc++.h>
using namespace std;
int n,m,k,t,mod;
int dp[25][25];
int fact[600005];
int invfact[600005];
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;
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;
fact[0] = 1;
invfact[0] = 1;
for(int i=1;i<600005;i++){
fact[i] = 1ll*fact[i-1]*i%mod;
invfact[i] = binpow(fact[i],mod-2);
}
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:73: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]
73 | for(int i=1;i<v.size();i++){
| ~^~~~~~~~~
turtle.cpp:76: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]
76 | for(int x = t+1;x>=1 - (i == v.size()-1);x--){
| ~~^~~~~~~~~~~~~
turtle.cpp:80: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]
80 | 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 |
45 ms |
7772 KB |
Output is correct |
| 2 |
Incorrect |
200 ms |
7588 KB |
Output isn't correct |
| 3 |
Correct |
102 ms |
7668 KB |
Output is correct |
| 4 |
Correct |
376 ms |
7624 KB |
Output is correct |
| 5 |
Correct |
856 ms |
7564 KB |
Output is correct |
| 6 |
Incorrect |
278 ms |
7624 KB |
Output isn't correct |
| 7 |
Correct |
479 ms |
7676 KB |
Output is correct |
| 8 |
Correct |
265 ms |
7632 KB |
Output is correct |
| 9 |
Correct |
450 ms |
7600 KB |
Output is correct |
| 10 |
Correct |
428 ms |
7652 KB |
Output is correct |
| 11 |
Execution timed out |
2082 ms |
7592 KB |
Time limit exceeded |
| 12 |
Execution timed out |
2085 ms |
7628 KB |
Time limit exceeded |
| 13 |
Execution timed out |
2059 ms |
7584 KB |
Time limit exceeded |
| 14 |
Execution timed out |
2082 ms |
7624 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2084 ms |
7624 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2087 ms |
7624 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2096 ms |
7752 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2080 ms |
7680 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2095 ms |
7632 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2066 ms |
7668 KB |
Time limit exceeded |
