oj.uz

답안 #316585

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
316585 2020-10-26T18:21:33 Z ehab_fawzy 힘 센 거북 (IZhO11_turtle) C++14
100 / 100
 931 ms 6136 KB 
//#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define pb push_back
#define ll long long
#define all(x) x.begin() , x.end()
#define rep(i,s,e) for (int i = s; i < e; ++i)
#define rev(i,s,e) for (int i = s; i > e; --i)
#define mem(a,v) memset(a , v , sizeof a)
#define negmod(x,m) ((x%m + m)%m)
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
        tree_order_statistics_node_update>;

const int N = 25 , M = 7e5 + 9;

ll n , m , k , t, mod , paths[N][N];
vector<pair<ll,ll>> points;

ll add( ll x , ll y ){
    ll ret = x + y;
    while ( ret >= mod ) ret -= mod;
    while ( ret <  0   ) ret += mod;
    return ret;
}
ll mul( ll x , ll y ){
    ll ret = x * y;
    if ( ret >= mod ) ret %= mod;
    if ( ret <  0   ) ret  = negmod(ret , mod);
    return ret;
}

inline ll pwr( ll x , ll y ){
    if ( y == 0 ) return mul(1 , 1);
    if ( y == 1 ) return mul(x , 1);
    return mul( (y&1 ? x : 1) , pwr( mul(x,x) , y >> 1 ) );
}

int pr[M] , comp[M] , ptr;
void linear_sieve() {
    for (int i = 2; i < M; ++i) {
        if (!comp[i]) pr[ptr++] = i , comp[i] = i;
        rep(j, 0, ptr) {
            ll mul = 1LL * i * pr[j];
            if (mul > M) break;
            comp[mul] = pr[j];
            if (i % pr[j] == 0) break;
        }
    }
}

int factorsCnt[M] , lst[M] , itr;
ll pCr( ll P , ll R ){
    if ( P < R ) return 0;
    if ( P < 0 or R < 0 ) return 0;
    itr = 0; ll df = P - R , cur;
    for ( int i = P; i > 1; --i ){
        cur = i;
        while ( cur > 1 ){
            if ( factorsCnt[comp[cur]]++ == 0 )
                lst[itr++] = comp[cur];
            cur /= comp[cur];
        }
    }
    int scale ;
    for ( int i = max(R , df); i > 1; --i ){
        scale = (i <= R) + (i <= df); cur = i;
        while ( cur > 1 ){
            factorsCnt[comp[cur]] -= scale;
            cur /= comp[cur];
        }
    }

    ll ans = 1;
    while ( ~--itr ){
        if ( factorsCnt[lst[itr]] > 0 ){
            ans = mul(ans , pwr(lst[itr] , factorsCnt[lst[itr]])) ;
        }
        factorsCnt[lst[itr]] = 0;
    }
    return ans ;
}

ll pathsCnt( int i , int j ){
    ll X = points[j].F - points[i].F + 1;
    ll Y = points[j].S - points[i].S + 1;
    ll P = X + Y - 2 , R = X - 1;
    return pCr(P , R);
}

ll dp[N][N][N];

int main() {
//    freopen("turtle.in"  , "r" , stdin );
//    freopen("turtle.out" , "w" , stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef CLion
    freopen("input.txt" , "r" , stdin);
//    freopen("output.txt", "w" , stdout);
#endif

    linear_sieve();
    cin >> n >> m >> k >> t >> mod;
    rep(i,0,k){
        int x , y;
        cin >> x >> y;
        points.pb({x , y});
    }
    points.pb({0 , 0});
    points.pb({n , m});
    sort( all(points) );
    k = points.size();

    for ( int i = 0; i < k; ++i ){
        for ( int j = i + 1; j < k; ++j ){
            paths[i][j] = pathsCnt(i , j);
        }
    }

    for ( int i = 0; i < k; ++i ){
        for ( int j = i + 1; j < k; ++j ){
            dp[i][j][0] = paths[i][j];
            for ( int p = i + 1; p < j; ++p ){
                if ( points[p].S >= points[i].S and points[p].S <= points[j].S ){
                    dp[i][j][0] = add( dp[i][j][0] , -mul(dp[i][p][0] , paths[p][j]) );
                }
            }
        }
    }

    ll ans = dp[0][k - 1][0];
    for ( int steps = 1; steps <= t; ++steps ){
        for ( int i = 0; i < k; ++i ){
            for ( int j = i + 1; j < k; ++j ){
                for ( int p = i + 1; p < j; ++p ){
                    if ( points[p].S >= points[i].S and points[p].S <= points[j].S ){
                        dp[i][j][steps] = add( dp[i][j][steps] , mul(dp[i][p][0] , dp[p][j][steps - 1]) );
                    }
                }
            }
        }
        ans = add(ans , dp[0][k - 1][steps] );
    }

    cout << ans ;
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 3328 KB Output is correct
2 Correct 8 ms 3328 KB Output is correct
3 Correct 8 ms 3328 KB Output is correct
4 Correct 8 ms 3456 KB Output is correct
5 Correct 9 ms 3456 KB Output is correct
6 Correct 9 ms 3456 KB Output is correct
7 Correct 10 ms 3456 KB Output is correct
8 Correct 10 ms 3328 KB Output is correct
9 Correct 26 ms 3448 KB Output is correct
10 Correct 44 ms 3456 KB Output is correct
11 Correct 262 ms 4216 KB Output is correct
12 Correct 785 ms 6008 KB Output is correct
13 Correct 380 ms 5496 KB Output is correct
14 Correct 319 ms 4220 KB Output is correct
15 Correct 369 ms 4216 KB Output is correct
16 Correct 767 ms 5880 KB Output is correct
17 Correct 690 ms 5880 KB Output is correct
18 Correct 931 ms 6136 KB Output is correct
19 Correct 867 ms 6136 KB Output is correct
20 Correct 770 ms 6136 KB Output is correct