2023牛客寒假算法基础集训营6

A

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int x;
    std::cin >> x;

    if (x <= 7) {
        std::cout << "very easy\n";
    } else if (x <= 233) {
        std::cout << "easy\n";
    } else if (x <= 10032) {
        std::cout << "medium\n";
    } else if (x <= 114514) {
        std::cout << "hard\n";
    } else if (x <= 1919810) {
        std::cout << "very hard\n";
    } else {
        std::cout << "can not imagine\n";
    }
    
    return 0;
}

B

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 2E5;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::vector<std::vector<int>> fac(N + 1);
    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j += i) {
            fac[j].push_back(i);
        }
    }

    int n, q;
    std::cin >> n >> q;

    std::vector<int> a;
    std::vector<std::vector<int>> p(N + 1);

    auto add = [&](int x) {
        a.push_back(x);
        int pos = a.size();
        for (auto num : fac[x]) {
            p[num].push_back(pos);
        }
    };

    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;

        add(x);
    }
    
    for (int i = 0; i < q; i++) {
        int o, x;
        std::cin >> o >> x;
        
        if (o == 1) {
            add(x);
        } else {
            int j = std::lower_bound(p[a[x - 1]].begin(), p[a[x - 1]].end(), x) - p[a[x - 1]].begin();
            std::cout << (int) p[a[x - 1]].size() - j - 1 << '\n';
        }
    }

    return 0;
}

C

#include <bits/stdc++.h>

using i64 = long long;

constexpr int P = 1000000007;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(i64 x) : x(norm(x % P)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        i64 v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};
struct Comb {
    int n;
    std::vector<Z> _fac;
    std::vector<Z> _invfac;
    std::vector<Z> _inv;
    
    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }
    
    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    Z binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    if (n == 1) {
        std::cout << "1\n1\n";
        return 0;
    }

    Z ans = power(Z(2), n - 1) + (n % 2) * (n - 1) * comb.binom(n - 1, (n - 1) / 2);
    for (int i = 0; i <= (n - 2) / 2; i++) {
        ans += (4 * i + 1) * comb.binom(n - 1, i);
    }
    std::cout << ans << '\n';

    for (int i = 1; i <= n; i++) {
        if (i % 2 == 1) {
            std::cout << i << ' ';
        }
    }
    for (int i = n; i >= 1; i--) {
        if (i % 2 == 0) {
            std::cout << i << ' ';
        }
    }

    return 0;
}

F

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::priority_queue<int> q;
    std::vector<int> ans(4 * n);

    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        
        q.push(x);
    }

    for (int i = 0; i < 4 * n; i++) {
        int x = q.top();
        q.pop();
        q.push(__builtin_popcount(x));
        ans[i] = q.top();
    }

    for (int i = 0; i < m; i++) {
        int x;
        std::cin >> x;

        if (x >= 4 * n) {
            std::cout << 1 << '\n';
        } else {
            std::cout << ans[x - 1] << '\n';
        }
    }

    return 0;
}

G

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, k;
    std::cin >> n >> k;

    std::vector<int> a, b;
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;

        if (x > 0) {
            a.push_back(x);
        } else {
            b.push_back(x);
        }
    }
    sort(a.begin(), a.end(), std::greater());
    sort(b.begin(), b.end());

    if ((int) a.size() % 2 == 1) {
        b.push_back(a.back());
        a.pop_back();
    }

    std::vector<int> p;
    for (int i = 0; i < (int) a.size(); i += 2) {
        p.push_back(a[i] * a[i + 1]);
    }
    for (int i = 0; i < (int) b.size(); i += 2) {
        p.push_back(b[i] * b[i + 1]);
    }
    sort(p.begin(), p.end(), std::greater());

    int ans = 0;
    for (int i = 0; i < std::min(k, (int) p.size()); i++) {
        ans += p[i];
    }
    std::cout << ans << '\n';
    
    return 0;
}

H

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int x, l, r;
    std::cin >> x >> l >> r;

    std::cout << std::fixed << std::setprecision(12) << std::min(1., std::max(0, x - l) / (r - l + 1.)) << '\n';
    
    return 0;
}

L

#include <bits/stdc++.h>

using i64 = long long;

constexpr int P = 1000000007;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(i64 x) : x(norm(x % P)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        i64 v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};
struct Comb {
    int n;
    std::vector<Z> _fac;
    std::vector<Z> _invfac;
    std::vector<Z> _inv;
    
    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }
    
    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }
    
    Z fac(int m) {
        if (m > n) init(2 * m);
        return _fac[m];
    }
    Z invfac(int m) {
        if (m > n) init(2 * m);
        return _invfac[m];
    }
    Z inv(int m) {
        if (m > n) init(2 * m);
        return _inv[m];
    }
    Z binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
} comb;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;
    
    std::vector<std::array<int, 2>> a(m);
    for (int i = 0; i < m; i++) {
        std::cin >> a[i][0] >> a[i][1];
    }
    sort(a.begin(), a.end());

    std::vector<Z> f(m);
    for (int i = 0; i < m; i++) {
        auto [xi, yi] = a[i];
        f[i] = comb.binom(xi + yi - 2, xi - 1);
    }

    Z ans = power(Z(2), n - 1);
    for (int i = 0; i < m; i++) {
        auto [xi, yi] = a[i];
        for (int j = 0; j < i; j++) {
            auto [xj, yj] = a[j];
            if (xj <= xi && yj <= yi) {
                f[i] -= f[j] * comb.binom(xi + yi - xj - yj, xi - xj);
            }
        }
        ans -= f[i] * power(Z(2), n - xi - yi + 1);
    }
    std::cout << ans << '\n';
    
    return 0;
}