Submission #90167

#	Time	Username	Problem	Language	Result	Execution time	Memory
90167		popovicirobert	Energetic turtle (IZhO11_turtle)	C++14	100 / 100	887 ms	3776 KiB

turtle

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = (int) 3e5;
const int MAXK = 50;

bool ciur[2 * MAXN + 1];
vector <int> primes;
int z;

inline void mod(int &x) {
    if(x >= z)
        x -= z;
}

inline int lgput(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1) {
            ans = (1LL * ans * a) % z;
        }
        b >>= 1;
        a = (1LL * a * a) % z;
    }
    return ans;
}

inline void prec(int n) {
    int i, j;
    for(i = 2; i * i <= n; i++) {
        if(ciur[i] == 0) {
            for(j = i * i; j <= n; j += i) {
                ciur[j] = 1;
            }
        }
    }
    for(i = 2; i <= n; i++) {
        if(ciur[i] == 0) {
            primes.push_back(i);
        }
    }
}

int fr[2 * MAXN + 1];

inline void get(int n, int sign) {
    for(auto it : primes) {
        if(it > n) {
            break;
        }
        ll pw = it;
        while(pw <= n) {
            fr[it] += (n / pw) * sign;
            pw *= it;
        }
    }
}

inline int comb(int n, int k) {
    if(n < k) {
        return 0;
    }
    get(n, 1);
    get(k, -1);
    get(n - k, -1);
    int ans = 1;
    for(auto it : primes) {
        if(it > n) {
            break;
        }
        ans = (1LL * ans * lgput(it, fr[it])) % z;
        fr[it] = 0;
    }
    return ans;
}

struct Point {
    int x, y;
    bool operator <(const Point &other) const {
        if(x == other.x) {
            return y < other.y;
        }
        return x < other.x;
    }
};

Point c[MAXK + 1];
int dp[MAXK + 1][MAXK + 1], ways[MAXK + 1][MAXK + 1];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, j, n, m, k, t;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> k >> t >> z;
    prec(n + m);
    for(i = 1; i <= k; i++) {
        cin >> c[i].x >> c[i].y;
    }
    c[++k] = {0, 0};
    c[++k] = {n, m};
    sort(c + 1, c + k + 1);
    for(i = 1; i <= k; i++) {
        for(j = i; j <= k; j++) {
            ways[i][j] = comb(c[j].x - c[i].x + c[j].y - c[i].y, c[j].x - c[i].x);
            for(int p = i + 1; p < j; p++) {
                ways[i][j] -= (1LL * ways[i][p] * comb(c[j].x - c[p].x + c[j].y - c[p].y, c[j].x - c[p].x)) % z;
                ways[i][j] += z;
                mod(ways[i][j]);
            }
        }
    }
    dp[1][1] = 1;
    for(i = 2; i <= k; i++) {
        for(int nr = 1; nr <= min(k, t + 2); nr++) {
            for(j = i - 1; j >= 1; j--) {
                dp[i][nr] = (dp[i][nr] + 1LL * dp[j][nr - 1] * ways[j][i]) % z;
            }
        }
    }
    int ans = 0;
    for(i = 2; i <= t + 2; i++) {
        ans += dp[k][i];
        mod(ans);
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

• Subtask 1: 100 / 100