Submission #1109802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109802		Kirill22	Energetic turtle (IZhO11_turtle)	C++17	100 / 100	51 ms	33360 KiB

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 / 100