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

small은 쉽게 맞았는데, large는 상당히 헤매었다.

small

O(N^2)로 단순히 문제를 풀었더니 50점이 나왔었다

i 와 j 루프로, (i-j) * 2^x로 구하였더니 O(N^2)로 Large에서는 시간초과가 나왔다.

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define MOD 1000000007LL
using namespace std;
ll table[300001];
ll makeTable(ll n){
    ll& ret=table[n];
    if(ret!=0) return ret;
    if(n==0) return ret=1;
    if(n&(1<<0)) return ret=(2*makeTable((n-1)/2)*makeTable((n-1)/2))%MOD;
    return ret=(makeTable(n/2)*makeTable(n/2))%MOD;
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    vector<ll> v(n);
    for(int i=0;i<n;++i){
        cin>>v[i];
    }
    sort(v.begin(),v.end());
    ll ans=0;
    for(int i=0;i<n-1;++i){
        for(int j=i+1;j<n;++j){
            ll p=j-i-1;
            ll val=v[j]-v[i];
            if(p>0) {
                ans+=val*makeTable(p);
                ans=ans%MOD;
            }
            else {
                ans+=val;
                ans=ans%MOD;
            }
        }
    }
    cout<<ans;
}

large

어떻게 nC2를 효율적으로 구할까 생각을 했는데, (i-j) * 2^x이니까, 역으로 생각해서 2^x * i - 2^x * j 인것을 알 수 있었다.
그래서 그냥 루프를 한번 돌려서 모든 index에 대하여 구할 수 있게 되었다.

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define MOD 1000000007LL
using namespace std;
ll table[300001];
ll makeTable(ll n){
    ll& ret=table[n];
    if(ret!=0) return ret;
    if(n==0) return ret=1;
    if(n&(1<<0)) {
        ll tmp=makeTable((n-1)/2);

        return ret=(2*tmp*tmp)%MOD;
    }
    ll tmp=makeTable(n/2);
    return ret=(tmp*tmp)%MOD;
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    vector<ll> v(n);
    for(int i=0;i<n;++i){
        cin>>v[i];
    }
    sort(v.begin(),v.end());
    makeTable(n);
    ll ans=0;
    // (v[i]-v[j])*2^x
    // --> v[i]*2^x - v[j]*2^x
    for(int i=0;i<n;++i){
        ll fi=(v[i]*makeTable(i))%MOD;
        ll se=(v[n-1-i]*makeTable(i))%MOD;
        ans=(ans+fi-se+MOD)%MOD;
    }
    cout<<ans;
}