답안 #958693

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
958693 2024-04-06T11:21:00 Z adaawf 힘 센 거북 (IZhO11_turtle) C++14
50 / 100
411 ms 188248 KB
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int a[25], b[25], c[600005][10], d[600005][10];
long long int f[600005][10], g[600005][10], p[600005][10], dd[25][25], z;
vector<pair<int, int>> v;
vector<int> vv, va;
long long int power(long long int x, long long int y, long long int mod = z) {
    long long int res = 1, h = x;
    while (y) {
        if (y & 1) res = res * h % mod;
        h = h * h % mod;
        y >>= 1;
    }
    return res;
}
long long int C(long long int n, long long int k) {
    vector<long long int> res;
    for (int i = 0; i < v.size(); i++) {
        int h = c[n][i] - c[k][i] - c[n - k][i];
        if (h >= v[i].second) {
            res.push_back(0);
            continue;
        }
        res.push_back(f[n][i] * g[k][i] % vv[i] * g[n - k][i] % vv[i] * p[h][i] % vv[i]);
    }
    long long int h = 0;
    for (int i = 0; i < v.size(); i++) {
        long long int k = z / vv[i];
        h = (h + res[i] * k % z * va[i]) % z;
    }
    return h;
}
bool check(int i, int j) {
    if (a[i] > a[j] || b[i] > b[j]) return false;
    return true;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m, k, t, l;
    cin >> n >> m >> k >> t >> z;
    for (int i = 1; i <= k; i++) {
        cin >> a[i] >> b[i];
        v.push_back({a[i], b[i]});
    }
    sort(v.begin(), v.end());
    for (int i = 1; i <= k; i++) {
        a[i] = v[i - 1].first;
        b[i] = v[i - 1].second;
    }
    v.clear();
    l = z;
    int h = sqrt(z);
    for (int i = 2; i <= h; i++) {
        if (z % i == 0) {
            int c = 0;
            while (z % i == 0) {
                c++;
                z /= i;
            }
            v.push_back({i, c});
            int h = power(i, c, l);
            if (h == 0) h = l;
            vv.push_back(h);
        }
    }
    if (z != 1) v.push_back({z, 1}), vv.push_back(z);
    z = l;
    for (int i = 1; i <= n + m; i++) {
        for (int j = 0; j < v.size(); j++) {
            long long int h = v[j].first;
            while (h <= i) {
                c[i][j] += i / h;
                h *= v[j].first;
            }
            int k = i;
            while (k % v[j].first == 0) {
                k /= v[j].first;
            }
            d[i][j] = k;
        }
    }
    for (int j = 0; j < v.size(); j++) {
        va.push_back(power(z / vv[j], vv[j] - 2, vv[j]));
        f[0][j] = 1;
        for (int i = 1; i <= n + m; i++) {
            f[i][j] = f[i - 1][j] * d[i][j] % vv[j];
        }
        g[n + m][j] = power(f[n + m][j], vv[j] - 2, vv[j]);
        for (int i = n + m - 1; i >= 0; i--) {
            g[i][j] = g[i + 1][j] * d[i + 1][j] % vv[j];
        }
        p[0][j] = 1;
        for (int i = 1; i <= n + m; i++) {
            p[i][j] = 1ll * p[i - 1][j] * v[j].first % vv[j];
        }
    }
    a[k + 1] = n, b[k + 1] = m;
    k++;
    for (int i = 0; i < k; i++) {
        if (!check(i, i + 1)) continue;
        dd[i][i + 1] = C(a[i + 1] - a[i] + b[i + 1] - b[i], a[i + 1] - a[i]);
    }
    for (int d = 3; d <= k + 1; d++) {
        for (int i = 0; i <= k - d + 1; i++) {
            int j = i + d - 1;
            if (!check(i, j)) continue;
            dd[i][j] = C(a[j] - a[i] + b[j] - b[i], a[j] - a[i]);
            for (int l = i + 1; l < j; l++) {
                if (!check(i, l)) continue;
                dd[i][j] = (dd[i][j] + z - C(a[l] - a[i] + b[l] - b[i], a[l] - a[i]) * dd[l][j] % z) % z;
            }
        }
    }
    long long int res = 0;
    for (int i = 0; i < (1 << (k + 1)); i++) {
        int h = __builtin_popcount(i);
        if (h > t + 2) continue;
        if (!(i & 1) || !(i & (1 << k))) continue;
        vector<int> v;
        long long int c = 1;
        for (int j = 0; j <= k; j++) {
            if (i & (1 << j)) {
                v.push_back(j);
            }
        }
        for (int i = 1; i < v.size(); i++) {
            c *= dd[v[i - 1]][v[i]];
            c %= z;
        }
        res = (res + c) % z;
    }
    cout << res;
}

Compilation message

turtle.cpp: In function 'long long int C(long long int, long long int)':
turtle.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
turtle.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
turtle.cpp: In function 'int main()':
turtle.cpp:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int j = 0; j < v.size(); j++) {
      |                         ~~^~~~~~~~~~
turtle.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int j = 0; j < v.size(); j++) {
      |                     ~~^~~~~~~~~~
turtle.cpp:130:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         for (int i = 1; i < v.size(); i++) {
      |                         ~~^~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 6492 KB Output isn't correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 7 ms 6492 KB Output is correct
5 Correct 260 ms 6492 KB Output is correct
6 Correct 2 ms 6488 KB Output is correct
7 Correct 15 ms 6488 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 27 ms 12892 KB Output is correct
10 Correct 43 ms 12892 KB Output is correct
11 Correct 47 ms 64080 KB Output is correct
12 Correct 179 ms 178560 KB Output is correct
13 Incorrect 122 ms 163664 KB Output isn't correct
14 Incorrect 79 ms 72056 KB Output isn't correct
15 Incorrect 325 ms 72052 KB Output isn't correct
16 Incorrect 149 ms 186960 KB Output isn't correct
17 Incorrect 137 ms 179964 KB Output isn't correct
18 Incorrect 161 ms 188244 KB Output isn't correct
19 Incorrect 220 ms 188248 KB Output isn't correct
20 Incorrect 411 ms 188200 KB Output isn't correct