QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#634#417099#8723. 乘二debateCappsFailed.2024-05-24 13:30:232024-05-24 13:30:23

详细

Extra Test:

Accepted
time: 487ms
memory: 10412kb

input:

200000 688425072
24796 7405 8339 32066 17088 26710 15187 17745 29669 16949 18961 5955 2503 19102 2787 7655 5326 24046 32768 19623 3212 24578 24101 9309 20799 18342 14903 14952 26270 32336 14889 13822 19410 26639 19744 14275 5314 10174 11989 24475 10387 29565 14907 25789 18799 3426 20323 29706 18822 ...

output:

143294016

result:

ok 1 number(s): "143294016"

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#417099#8723. 乘二Capps#AC ✓428ms10908kbC++203.1kb2024-05-22 14:19:052024-05-22 14:19:05

answer

#include <bits/stdc++.h>

using i64 = long long;

using ld = long double;

template <class T, T P>
class Comb {
    static constexpr int multip(const int &a, const int &b) {
        return 1ll * a * b % P;
    }
    static constexpr i64 multip(const i64 &a, const i64 &b) {
        i64 res = a * b - i64(1.L * a * b / P) * P;
        res %= P;
        res += (res < 0 ? P : 0);
        return res;
    }

    int n;
    std::vector<T> _jc, _ijc, _inv;

public:
    constexpr Comb() : n{0}, _jc{1}, _ijc{1}, _inv{0} {}
    Comb(int n) : Comb() {
        init(n);
    }

    static constexpr T powp(T a, i64 mi) {
        T ans = 1;
        for (; mi; mi >>= 1, a = multip(a, a))
            if (mi & 1)
                ans = multip(ans, a);
        return ans;
    }

    void init(int m) {
        m = std::min(m, P - 1);
        if (m <= n)
            return;

        _jc.resize(m + 1);
        _ijc.resize(m + 1);
        _inv.resize(m + 1);

        for (int i = n + 1; i <= m; i++) {
            _jc[i] = multip(i, _jc[i - 1]);
        }
        _ijc.back() = powp(_jc.back(), P - 2);
        for (int i = m; i > n; i--) {
            _ijc[i - 1] = multip(i, _ijc[i]);
            _inv[i] = multip(_ijc[i], _jc[i - 1]);
        }

        n = m;
    }

    T jc(int x) {
        if (x > n)
            init(x << 1);
        return _jc[x];
    }
    T ijc(int x) {
        if (x > n)
            init(x << 1);
        return _ijc[x];
    }
    T inv(int x) {
        if (x > n)
            init(x << 1);
        return _inv[x];
    }

    T A(int a, int b) {
        if (a < b or b < 0)
            return 0;
        return multip(jc(a), ijc(a - b));
    }
    T C(int a, int b) {
        if (a < b or b < 0)
            return 0;
        return multip(A(a, b), ijc(b));
    }
};

int add(int a, int b, const int Mod) {
    a += b;

    if (a >= Mod) {
        a -= Mod;
    }

    if (a < 0) {
        a += Mod;
    }

    return a;
}

constexpr int P = int(1e9) + 7;

int add(int a, int b) {
    a += b;

    if (a >= P) {
        a -= P;
    }

    if (a < 0) {
        a += P;
    }

    return a;
}

Comb<int, P> comb;

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

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

    std::vector<i64> a(n);

    std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<>> q;

    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        q.emplace(a[i], i);
    }

    while (q.top().first < (1 << 30) and k > 0) {
        int x = q.top().second;
        q.pop();

        k -= 1;
        a[x] *= 2;
        q.emplace(a[x], x);
    }

    std::vector<int> pos(n);
    std::iota(begin(pos), end(pos), 0);

    std::sort(begin(pos), end(pos), [&](int x, int y) {
        return a[x] < a[y];
    });

    int answer = 0;
    for (int i = 0; i < n; i++) {
        int x = pos[i];

        int y = (i < k % n) + k / n;
        answer = add(answer, a[x] % P * comb.powp(2, y) % P);
    }

    std::cout << answer;

    return 0;
}