AtCoder Beginner Contest 147 F - Sum Difference

問題ページ
0-originで考える． より， となる． は一定なので，結局 が取りうる値の種類数を数えられればよいことがわかる．

例として要素を3個 選んだときの について考える．これは となる． が取りうる値は， 以上， 以下となる． は1刻みで値を変えられるので，うまく値を動かすと は 以上 以下の全ての値を取ることが出来る．一般に要素を 個選んだ場合， 以上 以下の全ての値を取ることができる．

選んだ要素の和 が取る値の mod D は一定で， となる．mod の値ごとに の値を保存しておき，この和集合を取ればよい． をソートして，隣接する区間が交差するならマージする操作を繰り返すことでこれは求まる．

mod D で分類するのが思いつかなかった…

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n, x, d;  
    cin >> n >> x >> d;  
  
    if(d == 0) {  
        if(x == 0) cout << 1 << endl;  
        else cout << n+1 << endl;  
        return 0;  
    }  
  
    if(d < 0) x *= -1, d *= -1;  
  
    map<ll,vector<PII>> mp;  
    REP(i, n+1) {  
        // i個選ぶとき  
        // i*x + d(0 + 1 + … + i-1) ～ i*x + d(n-1-i + n-i + … + n-1)  
        ll lb = i*x/d + i*(i-1)/2;  
        ll ub = i*x/d + n*i - i*(i+1)/2;  
        ll mo = ((i*x)%d+d)%d;  
        mp[mo].emplace_back(lb, ub);  
    }  
  
    ll ret = 0;  
    for(auto pv: mp) {  
        auto v = pv.second;  
        sort(ALL(v));  
        PII last = v[0];  
        vector<ll> nv;  
        FOR(i, 1, v.size()) {  
            if(v[i].first <= last.second) {  
                chmax(last.second, v[i].second);  
            } else {  
                ret += last.second - last.first + 1;  
                last = v[i];  
            }  
        }  
        ret += last.second - last.first + 1;  
    }  
    cout << ret << endl;  
  
    return 0;  
}