Submission #1109802

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1109802	2024-11-07T15:51:12 Z	Kirill22	Energetic turtle (IZhO11_turtle)	C++17	100 / 100	51 ms	33360 KB

turtle

#pragma GCC optimize("O3")
#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	36 ms	33104 KB	Output is correct
2	Correct	35 ms	33104 KB	Output is correct
3	Correct	41 ms	33240 KB	Output is correct
4	Correct	31 ms	33104 KB	Output is correct
5	Correct	32 ms	33220 KB	Output is correct
6	Correct	33 ms	33360 KB	Output is correct
7	Correct	33 ms	33144 KB	Output is correct
8	Correct	30 ms	33332 KB	Output is correct
9	Correct	44 ms	33108 KB	Output is correct
10	Correct	30 ms	33096 KB	Output is correct
11	Correct	31 ms	33096 KB	Output is correct
12	Correct	31 ms	33104 KB	Output is correct
13	Correct	36 ms	33104 KB	Output is correct
14	Correct	37 ms	33104 KB	Output is correct
15	Correct	38 ms	33096 KB	Output is correct
16	Correct	35 ms	33100 KB	Output is correct
17	Correct	35 ms	33092 KB	Output is correct
18	Correct	36 ms	33104 KB	Output is correct
19	Correct	38 ms	33104 KB	Output is correct
20	Correct	51 ms	33116 KB	Output is correct