[AtCoder] ABC 163 D – Sum of Large Numbers
問題
方針
\( 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; }
ディスカッション
コメント一覧
まだ、コメントがありません