oj.uz

Submission #1072959

# Submission time Handle Problem Language Result Execution time Memory
1072959 2024-08-24T07:50:55 Z coolboy19521 Energetic turtle (IZhO11_turtle) C++17
5 / 100
 2000 ms 2768 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[k], 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
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2516 KB Output is correct
2 Execution timed out 2083 ms 2436 KB Time limit exceeded
3 Execution timed out 2066 ms 2516 KB Time limit exceeded
4 Execution timed out 2069 ms 2516 KB Time limit exceeded
5 Execution timed out 2070 ms 2516 KB Time limit exceeded
6 Incorrect 5 ms 2512 KB Output isn't correct
7 Execution timed out 2020 ms 2512 KB Time limit exceeded
8 Execution timed out 2061 ms 2516 KB Time limit exceeded
9 Execution timed out 2053 ms 2516 KB Time limit exceeded
10 Execution timed out 2021 ms 2768 KB Time limit exceeded
11 Execution timed out 2045 ms 2512 KB Time limit exceeded
12 Execution timed out 2069 ms 2516 KB Time limit exceeded
13 Execution timed out 2008 ms 2768 KB Time limit exceeded
14 Incorrect 79 ms 2512 KB Output isn't correct
15 Execution timed out 2051 ms 2516 KB Time limit exceeded
16 Execution timed out 2064 ms 2516 KB Time limit exceeded
17 Execution timed out 2069 ms 2516 KB Time limit exceeded
18 Incorrect 195 ms 2516 KB Output isn't correct
19 Incorrect 189 ms 2384 KB Output isn't correct
20 Execution timed out 2064 ms 2516 KB Time limit exceeded