답안 #481073

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
481073 2021-10-19T11:51:37 Z FatihSolak 힘 센 거북 (IZhO11_turtle) C++17
100 / 100
64 ms 3052 KB
#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;
      |                                                         ~~^~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 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