Submission #1109785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109785		Kirill22	Energetic turtle (IZhO11_turtle)	C++17	5 / 100	323 ms	231888 KiB

turtle

#include "bits/stdc++.h"

using namespace std;

int mod;
int C[5000][5000];

int choose(int n, int k) {
    if (k > n || k < 0) {
        return 0;
    }
    return C[n][k];
}

void solve() {
    int n, m, k, t;
    cin >> n >> m >> k >> t >> mod;
    for (int i = 0; i < 5000; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) {
                C[i][j] = 1 % mod;
            } else {
                C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % 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<int> dp(1 << N);
    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<int> calc(1 << N);
    for (int msk = 0; msk < (1 << N); msk++) {
        int c = 1 % mod, prev = -1;
        for (int i = 0; i < N; i++) {
            if (msk >> i & 1) {
                if (prev != -1) {
                    c = c * 1ll * cnt[prev][i] % mod;
                }
                prev = i;
            }
        }
        calc[msk] = c;
    }
    vector<int> path(N + 1);
    vector<vector<int>> mem(N + 1);
    for (int msk = 0; msk < (1 << N); msk++) {
        if (msk >> (N - 1) & 1) {
            if (msk & 1) {
                if (calc[msk]) {
                    mem[__builtin_popcount(msk)].push_back(msk);
                }
            }
        }
    }
    for (int i = N; i >= 2; i--) {
        for (auto msk : mem[i]) {
            (path[i] += calc[msk]) %= mod;
        }
        for (int j = i + 1; j <= N; j++) {
            int val = choose(j - 2, i - 2) * 1ll * path[j] % mod;
            if (j % 2 != i % 2) {
                (path[i] += mod - val) %= mod;
            } else {
                (path[i] += val) %= mod;
            }
        }
//        cout << path[i] << endl;
    }
    int ans = 0;
    for (int i = 0; i <= min(N, t); i++) {
        (ans += path[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: 5 / 100