oj.uz

Submission #1073073

# Submission time Handle Problem Language Result Execution time Memory
1073073 2024-08-24T09:14:15 Z coolboy19521 Energetic turtle (IZhO11_turtle) C++17
25 / 100
 2000 ms 1504 KB 
// 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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1500 KB Output is correct
2 Execution timed out 2071 ms 1504 KB Time limit exceeded
3 Execution timed out 2040 ms 1500 KB Time limit exceeded
4 Execution timed out 2060 ms 1504 KB Time limit exceeded
5 Execution timed out 2054 ms 1500 KB Time limit exceeded
6 Correct 2 ms 1504 KB Output is correct
7 Execution timed out 2094 ms 1504 KB Time limit exceeded
8 Execution timed out 2021 ms 1500 KB Time limit exceeded
9 Execution timed out 2065 ms 1504 KB Time limit exceeded
10 Execution timed out 2073 ms 1504 KB Time limit exceeded
11 Execution timed out 2066 ms 1504 KB Time limit exceeded
12 Execution timed out 2072 ms 1504 KB Time limit exceeded
13 Execution timed out 2064 ms 1504 KB Time limit exceeded
14 Correct 9 ms 1504 KB Output is correct
15 Execution timed out 2093 ms 1504 KB Time limit exceeded
16 Execution timed out 2065 ms 1504 KB Time limit exceeded
17 Execution timed out 2069 ms 1504 KB Time limit exceeded
18 Correct 19 ms 1500 KB Output is correct
19 Correct 17 ms 1504 KB Output is correct
20 Execution timed out 2055 ms 1504 KB Time limit exceeded