Submission #44304584

---

Source Code Expand

#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <string>

#include <cmath>
#include <queue>
#include <stack>

#include <unordered_set>
#include <unordered_map>
#include <array>
#include <iomanip>

#include <atcoder/all>

using namespace std;

#define LL long long

inline int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') {
            f = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

inline void write(int x) {
	if (x < 0) {
		putchar('-'); x = -x;
	}
    static int sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48); 
}

inline void writeln(int x) {
	if (x < 0) {
		putchar('-'); x = -x;
	}
    static int sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48); 
	putchar('\n');
}

inline LL readll() {
    LL x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') {
            f = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}

inline void writell(LL x) {
	if (x < 0) {
		putchar('-'); x = -x;
	}
    static LL sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48); 
}

inline void writellln(LL x) {
	if (x < 0) {
		putchar('-'); x = -x;
	}
    static LL sta[35];
    int top = 0;
    do {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top) putchar(sta[--top] + 48); 
	putchar('\n');
}
template<class DataType1, class DataType2>
void write(pair<DataType1, DataType2> a, char endSplit = ' ') {
    cout << "(" << a.first << ", " << a.second << ")" << endSplit;
}
template<class DataType>
void write(vector<DataType> &a, char split = ' ', char endSplit = '\n') {
    for (int i = 0; i < a.size(); ++i) {
        cout << a[i] << split;
    }
    cout << endSplit;
}

using mint = atcoder::modint998244353;

LL getS(LL a, LL b, LL c, LL n) {
    if (n <= 0) {
        return 0;
    }
    if (n == 1) {
        return b / c;
    }
    LL tmp = 0;
    tmp += (a / c) * (n - 1) * n / 2;
    tmp += (b / c) * n;
    a = a % c;
    b = b % c;
    if (a == 0) {
        return tmp;
    } else {
        return tmp + getS(c, (a * n + b) % c, a, (a * n + b) / c);
    }
    // LL res = 0;
    // for (LL i = 0; i < n; ++i) {
    //     res += (b + i * a) / c;
    // }
    // return res;
}
int main() {
	// std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    int n = read();
    vector<LL> a(n);
    for (int i = 0; i < n; ++i) {
        a[i] = readll();
    }
    sort(a.begin(), a.end());
    LL last = 0;
    LL diff = 0;
    LL sum = 0;
    mint res = a[0] + 1;
    last = a[0];
    sum = a[0] * n;
    for (int i = 1; i < n; ++i) {
        // sum: bag size after lower last times
        // we can lower last + 1 ~ a[i] times
        if (a[i] == last) {
            continue;
        }
        // diff = a[i] - last;
        // lower last + 1 time
        LL diff = a[i] - last;
        LL d = n - i;
        // for (LL lower = last + 1; lower <= a[i]; ++lower) {
        // for (LL lower = 0; lower < diff; ++lower) {

        //     sum += (n - i);
        //     res += (sum / n) + 1;
        // }

        // sum + d, sum + 2d ... sum + diff * d
        // each over n
        // then +1
        res += diff;
        // (sum + d) / n, (sum + 2d) / n ... (sum + diff * d) / n
        res += getS(d, sum + d, n, diff);
        sum += (diff * d);
        last = a[i];
        // cout << res.val() << endl;
    }
    cout << res.val() << endl;
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:155:8: warning: unused variable ‘diff’ [-Wunused-variable]
  155 |     LL diff = 0;
      |        ^~~~

Judge Result