Submission #896470

#	Time	Username	Problem	Language	Result	Execution time	Memory
896470		Alcabel	Žarulje (COI15_zarulje)	C++17	100 / 100	176 ms	26120 KiB

zarulje

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;

struct Modint {
    int x;
    Modint() {
        x = 0;
    }
    Modint(int _x) {
        while (_x >= mod) {
            _x -= mod;
        }
        while (_x < 0) {
            _x += mod;
        }
        x = _x;
    }
    Modint(long long _x) {
        if (_x >= mod || _x <= -mod) {
            _x %= mod;
        }
        if (_x < 0) {
            _x += mod;
        }
        x = _x;
    }
    Modint operator+(const Modint& other) const {
        return Modint(x + other.x);
    }
    Modint operator*(const Modint& other) const {
        return Modint(x * 1ll * other.x);
    }
    void operator+=(const Modint& other) {
        *this = *this + other;
    }
    void operator*=(const Modint& other) {
        *this = *this * other;
    }
    Modint operator^(long long p) const {
        Modint res = 1, tmp = x;
        while (p > 0) {
            if (p & 1) {
                res *= tmp;
            }
            tmp *= tmp;
            p >>= 1;
        }
        return res;
    }
    Modint operator/(const Modint& other) const {
        return *this * (other ^ (mod - 2));
    }
    void operator/=(const Modint& other) {
        *this = *this / other;
    }
    ~Modint() {}
};
vector<Modint> fact, invFact;

void buildFact(int n) {
    fact.resize(n + 1);
    invFact.resize(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = fact[i - 1] * i;
        // cerr << "i: " << i << ", fact: " << fact[i].x << '\n';
    }
    invFact[n] = fact[n] ^ (mod - 2);
    for (int i = n; i > 0; --i) {
        invFact[i - 1] = invFact[i] * i;
    }
}

Modint C(int n, int k) {
    if (n < 0 || k < 0 || n < k) {
        return 0;
    }
    return fact[n] * invFact[k] * invFact[n - k];
}

void solve() {
    int n, k;
    cin >> n >> k;
    buildFact(n);
    // cerr << C(n, n / 2).x << '\n';
    vector<int> a(n), order(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        order[i] = i;
    }
    sort(order.begin(), order.end(), [&](const int& A, const int& B) {
        return make_pair(a[A], A) < make_pair(a[B], B);
    });
    vector<vector<int>> byVal(n);
    int difs = 0;
    for (int l = 0, r; l < n; ++l, ++difs) {
        r = l - 1;
        while (r + 1 < n && a[order[r + 1]] == a[order[l]]) {
            ++r;
            byVal[difs].emplace_back(order[r]);
        }
        l = r;
    }
    vector<Modint> ans(n, 1);
    set<int> borders = {-1, n};
    vector<Modint> modif(n, 1);
    for (int val = 0; val < difs; ++val) {
        int sz = byVal[val].size();
        // cerr << "val: " << a[byVal[val][0]] << '\n';
        for (int pos = 0, posL = 0, posR = 0; pos < sz; ++pos) {
            // cerr << "idx: " << byVal[val][pos] << '\n';
            auto it = borders.upper_bound(byVal[val][pos]);
            int bR = *it, bL = *(--it);
            while (byVal[val][posL] <= bL) {
                ++posL;
            }
            while (posR < sz && byVal[val][posR] < bR) {
                ++posR;
            }
            // cerr << "posL: " << posL << ", posR: " << posR << '\n';
            assert(posL <= pos && pos < posR);
            ans[byVal[val][pos]] *= C(posR - posL - 1, pos - posL);
            // cerr << ans[byVal[val][pos]].x << '\n';
            if (pos != 0) {
                if (byVal[val][pos - 1] > bL) {
                    // [byVal[val][pos - 1] + 1, byVal[val][pos] - 1]
                    modif[byVal[val][pos - 1] + 1] *= C(posR - posL, posR - pos);
                    modif[byVal[val][pos]] /= C(posR - posL, posR - pos);
                } else if (it != borders.begin() && *prev(it) < byVal[val][pos - 1]) {
                    int prevPosL = upper_bound(byVal[val].begin(), byVal[val].end(), *prev(it)) - byVal[val].begin();
                    // cerr << "!\n";
                    // cerr << "prevPosL: " << prevPosL << '\n';
                    ans[bL] *= C(posR - prevPosL, posR - pos);
                }
            }
        }
        // cerr << "modif: " << modif[0].x << '\n';
        for (const int& i : byVal[val]) {
            borders.insert(i);
        }
    }
    Modint tmp = 1;
    for (int i = 0; i < n; ++i) {
        tmp *= modif[i];
        // cerr << "i: " << i << ", tmp: " << tmp.x << '\n';
        ans[i] *= tmp;
    }
    while (k--) {
        int pos;
        cin >> pos;
        --pos;
        cout << ans[pos].x << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        cerr << "-----------\n";
        cout << "-----------\n";
    }
#else
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
#endif

    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 38 / 38
• Subtask 3: 40 / 40