Submission #481042

#	Time	Username	Problem	Language	Result	Execution time	Memory
481042		FatihSolak	Energetic turtle (IZhO11_turtle)	C++17	40 / 100	2096 ms	7772 KiB

turtle

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

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

• Subtask 1: 40 / 100