令 \(S_i \gets S_i \oplus T_i\),那么代价中 \(D\) 变成 \(S_i = 1\) 的 \(i\) 数量。转化为对所有 \(f(S)\) 求和,最后答案乘上 \(2^n\)。
考虑贪心地求 \(f(S)\)。肯定是先选择小的 \(C_i\),把 \(S_i\) 变成 \(0\)。正确性显然。下面把 \(C_i\) 从大到小排序。
考虑拆贡献。对于一个 \(C_i\),考虑它一共被算了多少次。显然 \(i\) 自己会贡献 \(2^{n - 1}\) 次(除去 \(S_i = 0\) 的情况),对于 \(j < i\),因为 \(C_j \ge C_i\),所以改变 \(S_i\) 时 \(S_j\) 必定还没被改变。有 \(2^{n - 2}\) 种情况使得 \(S_j = 1\),一共有 \(i - 1\) 个 \(j < i\) 的 \(j\),所以 \(C_i\) 的贡献系数就是 \(2^{n - 2} \times (i - 1) + 2^{n - 1}\)。
因此最后答案就是:
\[2^n \times \sum\limits_{i = 1}^n (2^{n - 2} \times (i - 1) + 2^{n - 1}) \times C_i
\]
code
// Problem: E - Change a Little Bit
// Contest: AtCoder - AtCoder Beginner Contest 150
// URL: https://atcoder.jp/contests/abc150/tasks/abc150_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const ll mod = 1000000007;
inline ll qpow(ll b, ll p) {
if (p < 0) {
return 0;
}
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, a[maxn];
void solve() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
sort(a + 1, a + n + 1, greater<ll>());
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ans = (ans + (qpow(2, n - 2) * (i - 1) % mod + qpow(2, n - 1)) % mod * a[i] % mod) % mod;
}
printf("%lld\n", ans * qpow(2, n) % mod);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner AtCoder Contest Change Littlebeginner atcoder contest change contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 310