[AtCoder - ABC163 D] Sum of Large Numbers

난이도: 960

 

태그

• Mathematics → Combinatorics

 

풀이

1. \( 10^{100} + m \)의 수들을 더할 때, 무언가 특징이 있지 않을까?

\( 10^{100} \)은 충분히 큰 수입니다.

\( \frac{200\,000 \times 200\,001}{2} \approx 2 \times 10^{10} \)임을 감안하면 더더욱이요.

 

선택 방식을 약간 바꿔서 \( 0 \)부터 \( N \)까지 중에서 \( A_1, A_2, \ldots, A_K \)를 선택한 뒤

각각의 수에 \( 10^{100} \)을 더하고선 이의 합을 구한다면,

\( \sum\limits_{k=1}^{K} 10^{100} + A_k = 10^{100}K + \sum\limits_{k=1}^{k} A_k \)가 됩니다.

 

이는, 이 수들의 합이 대강 [선택한 수의 개수][충분한 양의 0][선택한 수의 합]으로 표현됨을 의미합니다.

다르게 말하자면, (선택한 수의 개수, 선택한 수의 합)이라는 순서쌍으로 나타낼 수 있겠죠.

 

2. 그럼, 가능한 경우의 수는?

\( K \)개의 수를 선택한다고 해봅시다.

[1]에서의 순서쌍을 생각해보면, 이의 앞부분인 선택한 수의 개수는 고정됩니다.

 

그럼, \( 0 \) 이상 \( N \) 이하의 수 중 \( K \)개의 수를 선택할 때 만들 수 있는 수의 개수는 몇 개일까요?

 

이거만 생각하긴 어려우니, 일단 최솟값과 최댓값부터 구해봅시다.

이는 간단한데, 최솟값은 가장 작은 \( K \)개의 합이고, 최댓값은 가장 큰 \( K \)개의 합입니다.

 

그리고, 최솟값과 최댓값 사이의 모든 수를 만들 수 있습니다.

최솟값의 합에서부터 시작해서, 원하는 값이 만들어질 때까지 (값을 더할 수 있는) 맨 뒤의 원소에 1씩 더하는 걸 생각해보세요.

 

즉, 가능한 경우의 수는 최댓값 - 최솟값 + 1로 구할 수 있습니다.

 

물론 실제 문제에서 구해야 하는 건 \( K \)개 이상의 수를 선택하는 것이므로,

\( K \)부터 \( N \)까지 돌리면서 가능한 경우의 합을 구해야겠죠.

// 이렇게 만들어진 순서쌍에서 겹치는 건 없으니, 걱정하지 않아도 됩니다.

// 선택한 수의 개수가 다르거나, 개수가 같으면 합이 다르기 때문이죠.

 

3. 코드

const ll mod = 1e9 + 7;
inline ll f(ll n){ return n*(n-1) / 2 %mod; }
 
void Main(){
    int n, k; cin >> n >> k;
    ll ans = 0;
    for (int m = k; m <= n+1; m++){
        ll mx = f(m) + (n-m+1LL)*m;
        ll mn = f(m);
        ans += (mx-mn+1); ans %= mod;
    }
    cout << ans;
}