oj.uz

답안 #1073001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1073001 2024-08-24T08:21:00 Z coolboy19521 힘 센 거북 (IZhO11_turtle) C++17
25 / 100
 2000 ms 2516 KB 
// Thanks Benq

#include "bits/stdc++.h"
#define ll long long
#define int ll

using namespace std;

const int sz = 1e6 + 6;
const int sm = 22;

vector<pair<int,int>> vp;
vector<int> ps;
int x[sz], y[sz];
ll wz[sm][sm];
ll dp[sm][sm];
bool sv[sz];

ll bpw(ll x, ll b, ll z) {
    ll r = 1;
    while (b) {
        if (b & 1)
            (r *= x) %= z;
        (x *= x) %= z;
        b >>= 1;
    }
    return r;
}

ll nck(ll n, ll k, ll z) {
    if (n < k || n < 0) return 0;
    if (k == 0 || n == k) return 1;
	if (k == 1 || k == n - 1) return n;
    ll r = 1;
    for (ll i = 0; i < (ll) ps.size(); i ++) {
        ll p = ps[i], e = 0;
        if (p > n) break;
        for (ll c = p; c <= n; c *= p)
            e += n / c;
        for (ll c = p; c <= k; c *= p)
            e -= k / c;
        for (ll c = p; c <= (n - k); c *= p)
            e -= (n - k) / c;
        (r *= bpw(p, e, z)) %= z;
    }
    return r;
}

ll gt(pair<int,int> f, pair<int,int> s, int z) {
    int xds = s.first - f.first;
    int yds = s.second - f.second;
    return nck(xds + yds, yds, z);
}

ll sb(ll a, ll b, ll z) {
    return (a + z - b) % z;
}

ll ml(ll a, ll b, ll z) {
    return a * b % z;
}

ll ad(ll a, ll b, ll z) {
    return (a + b) % z;
}

signed main() {
    for (ll i = 2; i < sz; i ++) {
        if (sv[i]) continue;
        ps.push_back(i);
        sv[i] = true;
        for (ll j = i * i; j < sz; j += i)
            sv[j] = true;
    }

    ll n, m, k, t, z;
    cin >> n >> m >> k >> t >> z;

    for (int i = 0; i < k; i ++) {
        int x, y;
        cin >> x >> y;
        vp.push_back(make_pair(x, y));
    }

    vp.push_back(make_pair(0, 0));
    vp.push_back(make_pair(n, m));

    sort(begin(vp), end(vp));
    k = vp.size();

    for (int i = 1; i < k; i ++)
        for (int j = i - 1; 0 <= j; j --) {
            wz[j][i] = gt(vp[j], vp[i], z);
            for (int l = j + 1; l < i; l ++)
                wz[j][i] = sb(wz[j][i], ml(wz[j][l], gt(vp[l], vp[i], z), z), z);
        }

    dp[0][0] = 1;

    for (int i = 1; i < k; i ++)
        for (int j = 0; j < i; j ++)
            for (int l = 1; l <= t + 1; l ++)
                dp[i][l] = ad(dp[i][l], ml(dp[j][l - 1], wz[j][i], z), z);

    ll r = 0;

    for (int i = 1; i <= t + 1; i ++)
        r = ad(r, dp[k - 1][i], z);

    cout << r << '\n';
}

Subtask #1
25.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2512 KB Output is correct
2 Execution timed out 2016 ms 2516 KB Time limit exceeded
3 Execution timed out 2044 ms 2516 KB Time limit exceeded
4 Execution timed out 2045 ms 2512 KB Time limit exceeded
5 Execution timed out 2086 ms 2512 KB Time limit exceeded
6 Correct 4 ms 2516 KB Output is correct
7 Execution timed out 2093 ms 2516 KB Time limit exceeded
8 Execution timed out 2100 ms 2512 KB Time limit exceeded
9 Execution timed out 2053 ms 2512 KB Time limit exceeded
10 Execution timed out 2077 ms 2516 KB Time limit exceeded
11 Execution timed out 2047 ms 2512 KB Time limit exceeded
12 Execution timed out 2025 ms 2516 KB Time limit exceeded
13 Execution timed out 2049 ms 2512 KB Time limit exceeded
14 Correct 50 ms 2512 KB Output is correct
15 Execution timed out 2004 ms 2512 KB Time limit exceeded
16 Execution timed out 2041 ms 2512 KB Time limit exceeded
17 Execution timed out 2051 ms 2516 KB Time limit exceeded
18 Correct 151 ms 2512 KB Output is correct
19 Correct 140 ms 2516 KB Output is correct
20 Execution timed out 2078 ms 2512 KB Time limit exceeded