11881번: 지우개

https://www.acmicpc.net/problem/11881


$O(n+a)$

dp[i][j]: 길이가1~i인 변 중 j개를 선택해서 만들 수 있는 선분 길이 or 면적 or 부피 합
dp[i][j]=dp[i-1][j-1]*(i*(길이가 i인 항 개수)) + dp[i-1][j]

#include<cstdio>
#define mod 1000000007
int n, x, y, z, s[100001];
int main() {
    scanf("%d", &n);
    for (int i = 0, x; i<n; i++) scanf("%d", &x), s[x] = (s[x] + x) % mod;
    for (int i = 1; i <= 100000; i++) {
        z = (z + (long long)y*s[i]) % mod;
        y = (y + (long long)x*s[i]) % mod;
        x = (x + s[i]) % mod;
    }
    printf("%d", z);
    return 0;
}