Submission #1073042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073042		coolboy19521	Energetic turtle (IZhO11_turtle)	C++17	0 / 100	21 ms	21716 KiB

turtle

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

using namespace std;

const int sz = 6e5 + 2;
const int sm = 30;

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

ll fact[sz], inv_fact[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;
}

void precompute_factorials(ll z) {
    fact[0] = inv_fact[0] = 1;
    for (ll i = 1; i < sz; i++) {
        fact[i] = fact[i - 1] * i % z;
    }
    inv_fact[sz - 1] = bpw(fact[sz - 1], z - 2, z);  // Fermat's little theorem for inverse
    for (ll i = sz - 2; i >= 1; i--) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % z;
    }
}

ll nck(ll n, ll k, ll z) {
    if (n < k || n < 0) return 0;
    return fact[n] * inv_fact[k] % z * inv_fact[n - k] % z;
}

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;

    precompute_factorials(z);  // Precompute factorials and their inverses modulo 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; j >= 0; 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 l = 1; l <= t + 1; l++) {
            for (int j = 0; j < i; j++) {
                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: 0 / 100