Submission #1073073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073073		coolboy19521	Energetic turtle (IZhO11_turtle)	C++17	25 / 100	2094 ms	1504 KiB

turtle

// Thanks Benq

#pragma GCC optimize("Ofast")
#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 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() {
    cin.tie(nullptr)->sync_with_stdio(false);
 
    ll n, m, k, t, z;
    cin >> n >> m >> k >> t >> z;
    // int sd = n + m + 2;
    int sd = sz;
 
    for (ll i = 2; i < sd; i ++) {
        if (sv[i]) continue;
        ps.push_back(i);
        sv[i] = true;
        for (ll j = i * i; j < sd; j += i)
            sv[j] = true;
    }
 
    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 ++) {
        vector<int> an(k + 2);
        for (int j = i - 1; 0 <= j; j --) {
            wz[j][i] = an[j] = 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], an[l], z), z);
        }
    }
 
    dp[0][1] = 1;
 
    for (int i = 1; i < k; i ++)
        for (int j = 0; j < i; j ++)
            for (int l = 2; l <= t + 2; 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 + 2; i ++)
        r = ad(r, dp[k - 1][i], z);

    // cout << ps.size() << '\n';
    cout << r << '\n';
}

• Subtask 1: 25 / 100