# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
481056 | FatihSolak | Energetic turtle (IZhO11_turtle) | C++17 | 63 ms | 3072 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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(long long 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;
u *= tmp;
}
ret = 1ll*ret * binpow(tmp,cnt)%mod;
}
return ret;
}
int val[25][25];
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});
}
nCr(600000,300000);
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 = 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)]*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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |