oj.uz

Submission #90165

# Submission time Handle Problem Language Result Execution time Memory
90165 2018-12-20T17:09:09 Z popovicirobert Energetic turtle (IZhO11_turtle) C++14
5 / 100
 316 ms 3656 KB 
#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[p].x - c[i].x + c[p].y - c[i].y, c[p].x - c[i].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
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Incorrect 3 ms 376 KB Output isn't correct
4 Incorrect 3 ms 376 KB Output isn't correct
5 Incorrect 5 ms 376 KB Output isn't correct
6 Incorrect 4 ms 376 KB Output isn't correct
7 Incorrect 6 ms 376 KB Output isn't correct
8 Incorrect 4 ms 376 KB Output isn't correct
9 Incorrect 26 ms 476 KB Output isn't correct
10 Incorrect 39 ms 488 KB Output isn't correct
11 Incorrect 129 ms 1584 KB Output isn't correct
12 Incorrect 167 ms 3576 KB Output isn't correct
13 Incorrect 70 ms 3096 KB Output isn't correct
14 Incorrect 165 ms 1588 KB Output isn't correct
15 Incorrect 194 ms 1576 KB Output isn't correct
16 Incorrect 219 ms 3500 KB Output isn't correct
17 Incorrect 184 ms 3412 KB Output isn't correct
18 Incorrect 316 ms 3652 KB Output isn't correct
19 Incorrect 288 ms 3656 KB Output isn't correct
20 Incorrect 177 ms 3576 KB Output isn't correct