oj.uz

Submission #1109799

# Submission time Handle Problem Language Result Execution time Memory
1109799 2024-11-07T15:46:25 Z Kirill22 Energetic turtle (IZhO11_turtle) C++17
60 / 100
 117 ms 67156 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 = 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
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 33288 KB Output is correct
2 Correct 72 ms 33096 KB Output is correct
3 Correct 54 ms 33104 KB Output is correct
4 Correct 64 ms 33096 KB Output is correct
5 Correct 53 ms 33096 KB Output is correct
6 Correct 61 ms 33096 KB Output is correct
7 Correct 59 ms 33128 KB Output is correct
8 Correct 66 ms 33096 KB Output is correct
9 Correct 60 ms 33096 KB Output is correct
10 Correct 65 ms 33096 KB Output is correct
11 Correct 62 ms 33140 KB Output is correct
12 Correct 61 ms 33100 KB Output is correct
13 Runtime error 104 ms 67144 KB Execution killed with signal 8
14 Runtime error 109 ms 67036 KB Execution killed with signal 8
15 Runtime error 110 ms 67152 KB Execution killed with signal 8
16 Runtime error 103 ms 67144 KB Execution killed with signal 8
17 Runtime error 115 ms 67148 KB Execution killed with signal 8
18 Runtime error 117 ms 67156 KB Execution killed with signal 8
19 Runtime error 112 ms 67144 KB Execution killed with signal 8
20 Runtime error 113 ms 67144 KB Execution killed with signal 8