oj.uz

Submission #1109800

# Submission time Handle Problem Language Result Execution time Memory
1109800 2024-11-07T15:47:48 Z Kirill22 Energetic turtle (IZhO11_turtle) C++17
0 / 100
 2000 ms 23888 KB 
#include "bits/stdc++.h"

using namespace std;

const int SZ = (int) 6e5 + 22;
int mod;
vector<int> mem[SZ];
vector<pair<int, int>> primes;

int rev(int a, int m) {
    if (a == 1) {
        return 1;
    }
    return m - m * 1ll * rev(m % a, a) / a;
}

int choose(int n, int k) {
    if (k > n || k < 0) {
        return 0;
    }
    int res = mem[n].back();
    res = res * 1ll * rev(mem[k].back(), mod) % mod;
    res = res * 1ll * rev(mem[n - k].back(), mod) % mod;
    for (int i = 0; i < (int) primes.size(); i++) {
        int cnt = mem[n][i] - mem[k][i] - mem[n - k][i];
        while (cnt) {
            res = res * 1ll * primes[i].first % mod;
            cnt--;
        }
    }
    return res;
}

void solve() {
    int n, m, k, t;
    cin >> n >> m >> k >> t >> mod;
    if (mod == 1) {
        cout << 0 << '\n';
        return;
    }
    {
        int tmp = mod;
        for (int i = 2; i * i <= tmp; i++) {
            if (tmp % i == 0) {
                primes.push_back({i, 0});
                while (tmp % i == 0) {
                    primes.back().second++;
                    tmp /= i;
                }
            }
        }
        if (tmp > 1) {
            primes.push_back({tmp, 1});
        }
        int sz = (int) primes.size();
        mem[0].resize(sz + 1);
        mem[0].back() = 1;
        for (int i = 1; i < SZ; i++) {
            mem[i] = mem[i - 1];
            int g = 1;
            while (gcd(i, mod) > 1) {
                g *= gcd(i, mod);
                i /= gcd(i, mod);
            }
            mem[i].back() = mem[i].back() * 1ll * (i / g) % mod;
            for (int j = 0; j < sz; j++) {
                while (g % primes[j].first == 0) {
                    mem[i][j]++;
                    g /= primes[j].first;
                }
            }
        }
    }
    t += 2;
    vector<pair<int, int>> a = {{0, 0}, {n, m}};
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        a.push_back({x, y});
    }
    std::sort(a.begin(), a.end());
    const int N = (int) a.size();
    vector<vector<int>> cnt(N, vector<int> (N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (a[i].first <= a[j].first && a[i].second <= a[j].second) {
                cnt[i][j] = choose(a[j].first + a[j].second - a[i].first - a[i].second, a[j].first - a[i].first);
            }
        }
    }
    vector<vector<int>> DP(N, vector<int> (t + 1));
    DP[0][1] = 1;
    for (int i = 1; i < N; i++) {
        for (int j = 2; j <= t; j++) {
            for (int pr = 0; pr < i; pr++) {
                (DP[i][j] += DP[pr][j - 1] * 1ll * cnt[pr][i] % mod) %= mod;
            }
            for (int pr = 0; pr < i; pr++) {
                (DP[i][j] += mod - DP[pr][j] * 1ll * cnt[pr][i] % mod) %= mod;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= min(N, t); i++) {
        (ans += DP[N - 1][i]) %= mod;
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2035 ms 14416 KB Time limit exceeded
2 Execution timed out 2050 ms 14416 KB Time limit exceeded
3 Execution timed out 2061 ms 14928 KB Time limit exceeded
4 Execution timed out 2059 ms 23748 KB Time limit exceeded
5 Execution timed out 2067 ms 14928 KB Time limit exceeded
6 Execution timed out 2071 ms 23632 KB Time limit exceeded
7 Execution timed out 2072 ms 23784 KB Time limit exceeded
8 Execution timed out 2059 ms 23880 KB Time limit exceeded
9 Execution timed out 2050 ms 23888 KB Time limit exceeded
10 Execution timed out 2077 ms 23888 KB Time limit exceeded
11 Execution timed out 2063 ms 23632 KB Time limit exceeded
12 Execution timed out 2061 ms 23888 KB Time limit exceeded
13 Execution timed out 2059 ms 14416 KB Time limit exceeded
14 Execution timed out 2065 ms 14416 KB Time limit exceeded
15 Execution timed out 2048 ms 14416 KB Time limit exceeded
16 Execution timed out 2072 ms 14416 KB Time limit exceeded
17 Execution timed out 2069 ms 14416 KB Time limit exceeded
18 Execution timed out 2051 ms 14416 KB Time limit exceeded
19 Execution timed out 2071 ms 14416 KB Time limit exceeded
20 Execution timed out 2055 ms 14416 KB Time limit exceeded