QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#417866 | #8723. 乘二 | DeNeRATe | RE | 0ms | 0kb | C++14 | 1.7kb | 2024-05-22 23:58:09 | 2024-05-22 23:58:09 |
answer
#include <bits/stdc++.h>
#define mod (ll)(1e9 + 7)
#define lson (x << 1)
#define rson (x << 1 | 1)
#define ll long long
#define INF 0x3f3f3f3f
#define vi vector<int>
#define ep emplace_back
#define pii pair<int, int>
#define cl(x, y) memset(x, y, sizeof(x))
#define de(x) cerr << #x << " = " << x << " " << endl
#define rep(i, a, b) for(ll i = a; i <= b; i++)
#define per(i, a, b) for(ll i = a; i >= b; i--)
#define LOCAL_TEST freopen("stdout.txt", "w", stdout)
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define MULTI_TEST int _;cin>>_;while(_--)CLEAN(),PROBLEM()
using namespace std;
const int maxn = 5e3 + 5;
inline ll fast(ll a, ll b) {
ll res = 1;
while(b) {
if(b & 1) res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
inline void CLEAN() {
}
inline void PROBLEM() {
int n, k;
cin >> n >> k;
vector<ll> arr(n + 1);
vi bit(n + 1, 0);
int cnt = 0, Max = 0;
rep(i, 1, n) {
cin >> arr[i];
per(j, 32, 0) {
if((arr[i] >> j) & 1) {
bit[i] = j;
Max = max(Max, bit[i]);
break;
}
}
}
rep(i, 1, n)
cnt += Max - bit[i];
ll ans = 0;
priority_queue<ll, vector<ll>, greater<> > mine;
rep(i, 1, n) mine.push(arr[i]);
ll lim = min(k, cnt);
while(lim--) {
ll now = mine.top();
mine.pop();
now *= 2ll;
mine.push(now);
}
if(cnt >= k) {
rep(i, 1, n) ans = (ans + mine.top()) % mod, mine.pop();
} else {
k -= cnt;
ll all = k / n, remain = k % n;
rep(i, 1, n) {
ans = (ans + mine.top() * fast(2ll, all + (i <= remain)) % mod) % mod;
mine.pop();
}
}
cout << ans << endl;
}
int main() {
IOS;
// MULTI_TEST;
PROBLEM();
system("pause");
return 0;
}
详细
Test #1:
score: 0
Dangerous Syscalls
input:
3 3 7 2 1
output:
15