[백준][C++] 15824: 너 봄에는 캡사이신이 맛있단다

문제 링크: https://www.acmicpc.net/problem/15824

(참고 링크)

 

N의 최대가 30만이기 때문에 조합을 다 만드는건 시간이 너무 많이 걸립니다

가능한 모든 조합에 대해 ((최대값 - 최소값)의 합)%mod를 구하는 문제인데, 각 수마다 가능한 조합이 몇 개 있을지 생각해봅시다.

일단 정렬 후, 스코빌 지수 x가 최대가 되는 조합의 수는 x보다 작은 수가 i개 있다고 했을 때 2^i개입니다. 동일하게 x가 최소가 되는 조합의 수는 x보다 큰 수가 j개 있다고 했을 때 2^j개입니다.

결과적으로 (2^i - 2^j) * x의 합을 구해주면 됩니다. 중간중간 모듈러 연산은 이 글을 참고해주시고, 2^i를 빠르게 구하려면 거듭제곱으로 구하면 됩니다. 자세한 건 이 게시물 참조해주세요. 그런데 푼 사람 코드를 보니 딱히 2^n을 안구해도 되나보네요.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MOD = 1000000007;


ll binpow(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1) res = (res*a) % MOD;

		a = (a*a) % MOD;
		b >>= 1;
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int n;
	cin >> n;
	vector<int> v(n);
	for (auto& c : v)
		cin >> c;
	sort(v.begin(), v.end());

	ll sum = 0;
	for (int i = 0; i < n; ++i) {
		ll max_cnt = binpow(2, i);
		ll min_cnt = binpow(2, n - i - 1);

		sum = (sum + (((max_cnt-min_cnt)%MOD) * (v[i]%MOD))%MOD + MOD)%MOD;
	}
	cout << sum << '\n';

	return 0;
}

모듈러 공식은 이 게시물 참고해주세요.