AtCoder Beginner Contest 163 ABC163 D - Sum of Large Numbers

atcoder.jp

個数と和が同じなら同じ数、個数が異なるなら和が同じでも異なる数にカウントする問題。

個選ぶと決め打ったとき、できる数は

前個の和と、後ろ個の和の間すべて

である。

これは簡単な帰納法で証明できる。

int main() {
    ll N, K;
    cin >> N >> K;
    mint ans = 0;
    vec<ll> mae(N+1);
    vec<ll> usi(N+1);
    mae[0] = 0;
    rep(i,N){
        mae[i+1] = mae[i]+i+1;
    }
    usi[0] = N;
    rep(i,N){
        usi[i+1] = usi[i] + N - 1 - i;
    }
    //先頭i個と後ろのi個の差
    for(ll i = K; i <= N+1; i++){
        ll l = mae[i-1];
        ll r = usi[i-1];
        ans += r - l + 1;
    }
    cout << ans << endl;
}