[AtCoder] ABC 163 D – Sum of Large Numbers

2020年12月14日

問題

方針

\( n \) 個の自然数から任意の個数の和の組み合わせは、

\[ \dfrac{n(n + 1)}{2}\]

となります。これは、最大値が \( n \) 個の和であるためです。ここで、関数 \( f(x) \) を

\[f(x) = \dfrac{x(x + 1)}{2}\]

とします。\( n \) 個の自然数から \( k \) 個の最大値は、\(f(n) – f(n – k)\) となり、最小値は、\( f(k) \) となるので、組み合わせは、

\[f(n) – f(n – k) – f(k) + 1\]

となります。これを \( k = K \) から \( k = N + 1 \) まで足し合わせれば良いです。

コード

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

ll f(ll n) {
    return n * (n + 1) / 2;
}

int main() {
    ll N, K;
    cin >> N >> K;
    ll mod = pow(10, 9) + 7;
    ll sum = 0;
    for (ll i = K; i <= N + 1; i++) {
        sum += f(N + 1) - f(N + 1 - i) - f(i) + 1;
        sum %= mod;
    }
    cout << sum << "\n";
    return 0;
}