Submission #1109801

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1109801	2024-11-07T15:49:43 Z	Kirill22	Energetic turtle (IZhO11_turtle)	C++17	100 / 100	54 ms	33344 KB

turtle

#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 tmp = i;
            for (int j = 0; j < sz; j++) {
                while (tmp % primes[j].first == 0) {
                    mem[i][j]++;
                    tmp /= primes[j].first;
                }
            }
            mem[i].back() = mem[i].back() * 1ll * tmp % mod;
        }
    }
    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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	33096 KB	Output is correct
2	Correct	54 ms	33228 KB	Output is correct
3	Correct	33 ms	33096 KB	Output is correct
4	Correct	34 ms	33096 KB	Output is correct
5	Correct	33 ms	33104 KB	Output is correct
6	Correct	34 ms	33096 KB	Output is correct
7	Correct	33 ms	33104 KB	Output is correct
8	Correct	32 ms	33176 KB	Output is correct
9	Correct	35 ms	33128 KB	Output is correct
10	Correct	33 ms	33132 KB	Output is correct
11	Correct	31 ms	33096 KB	Output is correct
12	Correct	32 ms	33100 KB	Output is correct
13	Correct	36 ms	33104 KB	Output is correct
14	Correct	35 ms	33296 KB	Output is correct
15	Correct	35 ms	33104 KB	Output is correct
16	Correct	35 ms	33344 KB	Output is correct
17	Correct	36 ms	33156 KB	Output is correct
18	Correct	36 ms	33156 KB	Output is correct
19	Correct	41 ms	33096 KB	Output is correct
20	Correct	37 ms	33096 KB	Output is correct