题解：AT_abc150_e [ABC150E] Change a Little Bit

· · 题解

一个显然的拆贡献，因为 S,T 的组合达到了 2^{400000}，考虑每一个 c_i 的贡献。

首先，对于一对特定的 S,T，有一个显然的贪心：肯定首先选择 c_i 较小的那一位修改。

由于改变 c 中元素的顺序不影响答案，将 c 从小到大排序，对于当前位 i，若 S_i = T_i，不需要改变，不产生贡献，于是只考虑 S_i \not = T_i 的情况。

对于第 1 至 i - 1 位，肯定优先于第 i 位改变，对当前的 D 没有影响。

对于第 i + 1 至 n 位，肯定优先选第 i 位改变，此时 D 即为 第 i + 1 至第 n 位不同位数的个数再加上第 i 位这一对。

此时在第 i+1 至第 n 位有 j 组不同的方案数即为 C_{n-i}^{j}，因为第 1 至 i - 1 位状态随意，则第 i+1 至第 n 位有 j 组不同，且第 1 至第 i - 1 位有任意组不同的总方案数即为 2^{i - 1} \times C_{n-i}^{j}，则该位的总贡献为：

\sum_{j=0}^{n-i} 2^{i - 1} \times C_{n-i}^{j} \times \Big (c_i \times (j+1) \Big)=c_i \times 2^{i - 1} \times \sum_{j=0}^{n-i} C_{n-i}^{j} \times (j+1)

最后的答案即为：

\sum_{i=1}^{n}c_i \times 2^{i - 1} \times \sum_{j=0}^{n-i} C_{n-i}^{j} \times (j+1)

此时 O(n) 预处理组合数，O(n^2) 计算答案，可以得到 70pts。

然后考虑优化。

令 f(x)=\displaystyle \sum_{j=0}^{x} C_{x}^{j} \times (j+1)，答案即为：

\sum_{i=1}^{n}c_i \times 2^{i - 1} \times f(n-i)

考虑如何快速求 f(x)。

\begin{aligned} f(x) &= \sum_{j=0}^{x} C_{x}^{j} \times (j+1) \\ &= \bigg(\sum_{j=0}^{x} C_{x}^{j} \times j \bigg ) + \bigg (\sum_{j=0}^{x} C_{x}^{j} \bigg ) \\ &= x \times 2^{x-1} + 2^{x} \end{aligned}

（不清楚原因的可以去背一背关于组合数的公式）

答案即为：

\sum_{i=1}^{n}c_i \times 2^{i - 1} \times \big( (n - i) \times 2^{n - i - 1} + 2^{n - i} \big)

但是你会发现输出 out 比答案 ans 小，可以计算发现 \frac{ans}{out}=2^n，很容易找到这个规律。

但是为什么呢？

我们会发现漏考虑了一个东西：我们枚举的是 S_i 和 T_i 不同的方案数。当 S_i=0,T_i=1 和 S_i=1,T_i=0 时，S_i 和 T_i 都算做不同，这是两种方案，而我们只算作了一种。同理，S_i 和 T_i 相同的也有两种情况。由于 S 和 T 有 n 位，所以答案需要乘上 2^{n}。

代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 200050, MOD = 1e9 + 7;

int qpow(int a, int b){
    int t = 1;
    for(; b; b >>= 1){
        if(b & 1) t = (ll)t * a % MOD;
        a = (ll)a * a % MOD;
    }
    return t;
}

int n, ans = 0, u = 0;
int a[N];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    sort(a + 1, a + n + 1); 
    for(int i = 1; i <= n; i ++){
        if(i < n) u = ((ll)(n - i) * qpow(2, n - i - 1) % MOD + qpow(2, n - i)) % MOD;
        else u = 1;
        ans = (ans + (ll)a[i] * qpow(2, i - 1) % MOD * u % MOD) % MOD;
    }
    cout << (ll)ans * qpow(2, n) % MOD;
    return 0;
}