让工资最小的 k=n-x-y 人前两年连续拿 C 被开除，幸存 x+y 人年年涨薪：前 x 大乘 3^m、接下来 y 大乘 2^m，取模输出。
OJ: roj
题目 ID: 10006
难度:普及
标签:贪心排序快速幂python
创建: 2026-10-02 17:43
更新: 2026-10-07 12:15
前置题目
luogu P2676[USACO07DEC] Bookshelf BB 复用 A 教的“先降序排序、再从最大元素开始取”的贪心：涨薪名额给工资最高的人最划算，故工资降序后取前 x 大之和，只是再叠加“开除最小的 n-x-y 人”与快速幂roj 1326【例7.5】取余运算（mod）B 的 main.cpp 里 ll power(ll base,ll exp)（exp&1 时 result 乘底数、底数自身平方取模、exp>>=1）正是 A 教的「二进制分解快速幂：底数逐位平方升级、位为 1 时把底数乘进答案」这一步，用来算 $3^m$、$2^m$（m 可达 1e9），B 只是在此外层叠加降序排序与「最小 k=n-x-y 人连续两年拿 C 被开除」的贪心结论与 m=1 特判。roj 1616「一本通 6.1 练习 1」A 的 B 次方B 的 main.cpp 中 ll power(ll base,ll exp)（result=result*base%MOD、base=base*base%MOD、exp>>=1）与 power(3,m)、power(2,m) 正是复用 A 教的「底数逐位平方、每一步取模」这一模快速幂步骤，用来把 m 年倍数 3^m、2^m 算成模值后代入 3^m S_x+2^m(S_{x+y}-S_x)；B 的 m 可达 1e9 使该步与 A 同样必要（main.py 用 pow(3,m,MOD)），另在其外叠加降序排序、前 k 大求和与剔除 k=n-x-y 人的贪心结论。
题目描述
公司有
样例：2 1 1 1 / 5 3 输出 21；2 2 0 0 / 5 2 输出 0。
思路
工资降序排序后，
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 18:07
# update_at: 2026-10-02 18:07
import sys
from itertools import accumulate
MOD = 10**9 + 7 # 答案模数
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, m, x, y = next(data), next(data), next(data), next(data)
# 工资降序排列；pre[j] = 前 j 大的工资之和
salary = sorted((next(data) for _ in range(n)), reverse=True)
pre = [0, *accumulate(salary)]
if m == 1:
# 只有一年：无人会连续两年拿 C，开除不会发生，拿 C 者照领原工资
ans = 3 * pre[x] + 2 * (pre[x + y] - pre[x]) + (pre[n] - pre[x + y])
else:
# 两年起：工资最小的 k = n-x-y 人在第 1、2 年连续拿 C 被开除，
# 幸存者恰好 x + y 人，此后年年涨薪，名额零浪费
three, two = pow(3, m, MOD), pow(2, m, MOD)
ans = three * pre[x] + two * (pre[x + y] - pre[x])
print(ans % MOD)
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-04 21:36
* update_at: 2026-10-04 21:36
*/
// main.cpp：工资降序后，m>=2 时把最小的 n-x-y 人连续两年拿 C 开除，
// 幸存者恰 x+y 人年年涨薪，答案为 3^m*S_x + 2^m*(S_{x+y}-S_x)；m=1 无人被开除需补上拿 C 者的原工资。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005; // n 的上界
const ll MOD = 1000000007; // 答案模数
ll salary[MAXN]; // salary[i] 表示工资降序后第 i 大的初始工资（下标从 1 开始）
ll pre[MAXN]; // pre[j] 表示工资最高的前 j 人的工资之和
// 快速幂：返回 base^exp mod MOD，用于计算 m 年的总倍数 3^m、2^m
ll power(ll base, ll exp) {
ll result = 1;
base %= MOD;
while (exp > 0) {
if (exp & 1) {
result = result * base % MOD;
}
base = base * base % MOD;
exp >>= 1;
}
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n, m, x, y;
cin >> n >> m >> x >> y;
for (ll i = 1; i <= n; i++) {
cin >> salary[i];
}
// 涨薪名额总是给当前工资最高的人最划算，故按工资从大到小排序
sort(salary + 1, salary + n + 1, greater<ll>());
for (ll i = 1; i <= n; i++) {
pre[i] = pre[i - 1] + salary[i];
}
ll ans;
if (m == 1) {
// 只有一年：不可能连续两年拿 C，无人被开除，拿 C 的人照领原工资
ans = 3 * (pre[x] % MOD) % MOD;
ans = (ans + 2 * ((pre[x + y] - pre[x]) % MOD)) % MOD;
ans = (ans + (pre[n] - pre[x + y]) % MOD) % MOD;
} else {
// 让最小的 k = n - x - y 人前两年连续拿 C 被开除，
// 此后在职者恰好 x + y 人年年涨薪：前 x 大总倍数 3^m，接下来 y 大总倍数 2^m
ll three = power(3, m);
ll two = power(2, m);
ans = three * (pre[x] % MOD) % MOD;
ans = (ans + two * ((pre[x + y] - pre[x]) % MOD)) % MOD;
}
cout << ans % MOD << '\n';
return 0;
}