oj.uz

답안 #1073042

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1073042 2024-08-24T08:53:45 Z coolboy19521 힘 센 거북 (IZhO11_turtle) C++17
0 / 100
 21 ms 21716 KB 
#include "bits/stdc++.h"
#define ll long long
#define int ll

using namespace std;

const int sz = 6e5 + 2;
const int sm = 30;

vector<pair<int, int>> vp;
vector<int> ps;
ll wz[sm][sm];
ll dp[sm][sm];
bool sv[sz];

ll fact[sz], inv_fact[sz];

ll bpw(ll x, ll b, ll z) {
    ll r = 1;
    while (b) {
        if (b & 1)
            (r *= x) %= z;
        (x *= x) %= z;
        b >>= 1;
    }
    return r;
}

void precompute_factorials(ll z) {
    fact[0] = inv_fact[0] = 1;
    for (ll i = 1; i < sz; i++) {
        fact[i] = fact[i - 1] * i % z;
    }
    inv_fact[sz - 1] = bpw(fact[sz - 1], z - 2, z);  // Fermat's little theorem for inverse
    for (ll i = sz - 2; i >= 1; i--) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % z;
    }
}

ll nck(ll n, ll k, ll z) {
    if (n < k || n < 0) return 0;
    return fact[n] * inv_fact[k] % z * inv_fact[n - k] % z;
}

ll gt(pair<int, int> f, pair<int, int> s, int z) {
    int xds = s.first - f.first;
    int yds = s.second - f.second;
    return nck(xds + yds, yds, z);
}

ll sb(ll a, ll b, ll z) {
    return (a + z - b) % z;
}

ll ml(ll a, ll b, ll z) {
    return a * b % z;
}

ll ad(ll a, ll b, ll z) {
    return (a + b) % z;
}

signed main() {
    for (ll i = 2; i < sz; i++) {
        if (sv[i]) continue;
        ps.push_back(i);
        sv[i] = true;
        for (ll j = i * i; j < sz; j += i)
            sv[j] = true;
    }

    ll n, m, k, t, z;
    cin >> n >> m >> k >> t >> z;

    precompute_factorials(z);  // Precompute factorials and their inverses modulo z

    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        vp.push_back(make_pair(x, y));
    }

    vp.push_back(make_pair(0, 0));
    vp.push_back(make_pair(n, m));

    sort(begin(vp), end(vp));
    k = vp.size();

    for (int i = 1; i < k; i++) {
        for (int j = i - 1; j >= 0; j--) {
            wz[j][i] = gt(vp[j], vp[i], z);
            for (int l = j + 1; l < i; l++) {
                wz[j][i] = sb(wz[j][i], ml(wz[j][l], gt(vp[l], vp[i], z), z), z);
            }
        }
    }

    dp[0][0] = 1;

    for (int i = 1; i < k; i++) {
        for (int l = 1; l <= t + 1; l++) {
            for (int j = 0; j < i; j++) {
                dp[i][l] = ad(dp[i][l], ml(dp[j][l - 1], wz[j][i], z), z);
            }
        }
    }

    ll r = 0;

    for (int i = 1; i <= t + 1; i++) {
        r = ad(r, dp[k - 1][i], z);
    }

    cout << r << '\n';
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 10712 KB Output isn't correct
2 Incorrect 12 ms 10708 KB Output isn't correct
3 Incorrect 11 ms 10728 KB Output isn't correct
4 Incorrect 15 ms 10704 KB Output isn't correct
5 Incorrect 11 ms 10704 KB Output isn't correct
6 Incorrect 14 ms 10708 KB Output isn't correct
7 Incorrect 12 ms 10708 KB Output isn't correct
8 Incorrect 13 ms 10900 KB Output isn't correct
9 Incorrect 12 ms 10932 KB Output isn't correct
10 Runtime error 20 ms 21716 KB Execution killed with signal 11
11 Runtime error 20 ms 21716 KB Execution killed with signal 11
12 Incorrect 10 ms 10708 KB Output isn't correct
13 Incorrect 12 ms 10864 KB Output isn't correct
14 Incorrect 11 ms 10708 KB Output isn't correct
15 Incorrect 13 ms 10700 KB Output isn't correct
16 Runtime error 20 ms 21700 KB Execution killed with signal 11
17 Runtime error 19 ms 21716 KB Execution killed with signal 11
18 Incorrect 13 ms 10772 KB Output isn't correct
19 Incorrect 10 ms 10708 KB Output isn't correct
20 Runtime error 21 ms 21596 KB Execution killed with signal 11