Submission #481073

#	Time	Username	Problem	Language	Result	Execution time	Memory
481073		FatihSolak	Energetic turtle (IZhO11_turtle)	C++17	100 / 100	64 ms	3052 KiB

turtle

#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 (stderr)

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;
      |                                                         ~~^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100