[C++] 11881 - 지우개

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

11881번: 지우개

 

 

ai < aj < ak를 만족시켜야 하므로

aj를 고정된 값으로 두고 ai와 ak를 더해서 곱해주는 형식으로 답을 구했다.

 

 

#include<bits/stdc++.h>
 
#define endl '\n'
#define mod 1000000007
 
using namespace std;
 
int COUNT[100005];
unsigned long long DP[1000005];
unsigned long long ans;
 
int main(void)
{
    int n, tmp;
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        cin >> tmp;
        COUNT[tmp]++;
    }
 
    for(int i = 1; i <= 100000; ++i)
        DP[i] = (DP[i-1] + i*COUNT[i]);
 
    for(int i = 1; i <= 100000; ++i)
        ans = (ans+((DP[i-1]*(DP[i]-DP[i-1])%mod)*(DP[100000]-DP[i])%mod)%mod)%mod;
 
    cout << ans << endl;
    
    return 0;
}