专栏文章

题解：AT_abc150_e [ABC150E] Change a Little Bit

JJHR100330
AT_abc150_e题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mio03i0d
此快照首次捕获于
2025/12/02 11:10
3 个月前
此快照最后确认于
2025/12/02 11:10
3 个月前
查看原文
一个显然的拆贡献，因为 S,TS,T 的组合达到了 24000002^{400000}，考虑每一个 cic_i 的贡献。
首先，对于一对特定的 S,TS,T，有一个显然的贪心：肯定首先选择 cic_i 较小的那一位修改。
由于改变 cc 中元素的顺序不影响答案，将 cc 从小到大排序，对于当前位 ii，若 Si=TiS_i = T_i，不需要改变，不产生贡献，于是只考虑 Si≠TiS_i \not = T_i 的情况。
对于第 11 至 i−1i - 1 位，肯定优先于第 ii 位改变，对当前的 DD 没有影响。
对于第 i+1i + 1 至 nn 位，肯定优先选第 ii 位改变，此时 DD 即为 第 i+1i + 1 至第 nn 位不同位数的个数再加上第 ii 位这一对。
此时在第 i+1i+1 至第 nn 位有 jj 组不同的方案数即为 Cn−ijC_{n-i}^{j}，因为第 11 至 i−1i - 1 位状态随意，则第 i+1i+1 至第 nn 位有 jj 组不同，且第 11 至第 i−1i - 1 位有任意组不同的总方案数即为 2i−1×Cn−ij2^{i - 1} \times C_{n-i}^{j}，则该位的总贡献为：
∑j=0n−i2i−1×Cn−ij×(ci×(j+1))=ci×2i−1×∑j=0n−iCn−ij×(j+1)\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)
最后的答案即为：
∑i=1nci×2i−1×∑j=0n−iCn−ij×(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) 预处理组合数，O(n2)O(n^2) 计算答案，可以得到 70pts70pts。
然后考虑优化。
令 f(x)=∑j=0xCxj×(j+1)f(x)=\displaystyle \sum_{j=0}^{x} C_{x}^{j} \times (j+1)，答案即为：
∑i=1nci×2i−1×f(n−i)\sum_{i=1}^{n}c_i \times 2^{i - 1} \times f(n-i)
考虑如何快速求 f(x)f(x)。
f(x)=∑j=0xCxj×(j+1)=(∑j=0xCxj×j)+(∑j=0xCxj)=x×2x−1+2x\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}
（不清楚原因的可以去背一背关于组合数的公式）
答案即为：
∑i=1nci×2i−1×((n−i)×2n−i−1+2n−i)\sum_{i=1}^{n}c_i \times 2^{i - 1} \times \big( (n - i) \times 2^{n - i - 1} + 2^{n - i} \big)
但是你会发现输出 outout 比答案 ansans 小，可以计算发现 ansout=2n\frac{ans}{out}=2^n，很容易找到这个规律。
但是为什么呢？
我们会发现漏考虑了一个东西：我们枚举的是 SiS_i 和 TiT_i 不同的方案数。当 Si=0,Ti=1S_i=0,T_i=1 和 Si=1,Ti=0S_i=1,T_i=0 时，SiS_i 和 TiT_i 都算做不同，这是两种方案，而我们只算作了一种。同理，SiS_i 和 TiT_i 相同的也有两种情况。由于 SS 和 TT 有 nn 位，所以答案需要乘上 2n2^{n}。

代码

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...