(mathcal{Description})
Link.
给定 ({x_n})，令
求出
(nle10^3)，(sum xle5 imes10^5)。
(mathcal{Solution})
太炫酷了叭。
令 (g(k)=f(k)-f(k-1))，断言这样一条性质：
甚至可以认为给原式洛了一发。
证明
假定存在 $c=lim_{k ightarrow+infty}frac{g(k)}{k^2}$，则对于任意 $varepsiloninmathbb R_+$，应有足够大的 $k$，使得 $(c-eps)k^2le g(k)le (c+eps)k^2$。继而，也应有足够大的 $k$ 使得 $(c-eps)sum_{ile k}i^2le f(k)le(c+eps)sum_{ile k}i^2$。考虑到 $sum_{ile k}i^2=frac{k^3}{3}+mathcal O(k^2)$，可以得到 $frac{1}{3}c-epsle frac{f(k)}{k^3}le frac{1}{3}c+eps$。所以基于这个假设，得到 $lim_{k ightarrow+infty}frac{f(k)}{k^3}=frac{1}{3}lim_{k ightarrow+infty}frac{g(k)}{k^2}$。此后，考虑使得 ((ax_i+b)mod k) 单增的 ((a,b))，根据取模的性质，应该有 (left{frac{ax_i+b}{k} ight}) 单增，其中 ({x}=x-lfloor x floor) 表示取非负数 (x) 的小数部分。所以，令 (alpha=frac{a}{k},eta=frac{b}{k})，我们仅需研究使得 ({alpha x_i+eta}) 单增的 ((alpha,eta)in[0,1)^2)。具体地，令
我们所求即为 (D) 的面积。
这步转化的具体数学原理我并没有学懂，这貌似也涉及了上文中“假定极限存在”的证明。当然存在一些感性理解方法也显得不够具有说服力。如果希望深刻研究请参考 官方题解 叭，这里先跳过，之后的步骤仍有思考价值。
我们把 ({y_i={alpha x_i+eta}}) 放在 ([0,1)) 这个关于 (1) 的“模域”上（Tiw: 你把“模”和“域”放一起是完全不合理的！我：？），进一步研究 ((alpha,eta)) 的性质：
可见，(alpha) 能决定 (y_i) 在圆周上的相对位置关系，而 (eta) 仅能整体旋转 (y)，也即是确定 (0) 的位置。显然，对于使得相对位置合法的 (alpha)，合法 (eta) 取值区间的长度为 ({alpha(x_1-x_n)})；另一方面，对于这样的 (alpha)，应有
同时，(alphain[0,1))，(x_iinmathbb N)，则 ({alpha x_{i+1}}-{alpha x_i}equiv{alpha(x_{i+1}-x_i)}pmod 1)，可见在 (alpha) 从 (0) 向 (1) 取值时，仅有经过某个 (frac{t}{|x_{i+1}-x_i|}) 会改变左式的值，即这些点把 ([0,1)) 分隔为若干区间，若一个区间合法，再积分求此时 (eta) 的贡献，即 (int_{l}^r{alpha(x_1-x_n)} ext dalpha)。注意 (|x_n-x_{n+1}|) 也在分隔点的分母中，所以这是单纯的一次函数积分。
最终，复杂度瓶颈为取出 (mathcal O(sum x)) 个区间排序，即 (mathcal O(sum xlogsum x))。
(mathcal{Code})
/*~Rainybunny~*/
#include <bits/stdc++.h>
#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )
const int MAXN = 1e3, MOD = 998244353, INV6 = 166374059;
int n, x[MAXN + 5];
inline int iabs( const int u ) { return u < 0 ? -u : u; }
inline int mul( const int u, const int v ) { return 1ll * u * v % MOD; }
inline int sub( int u, const int v ) { return ( u -= v ) < 0 ? u + MOD : u; }
inline int add( int u, const int v ) { return ( u += v ) < MOD ? u : u - MOD; }
inline int mpow( int u, int v = MOD - 2 ) {
int ret = 1;
for ( ; v; u = mul( u, u ), v >>= 1 ) ret = mul( ret, v & 1 ? u : 1 );
return ret;
}
struct Atom {
int a, b, c;
inline bool operator < ( const Atom& t ) const {
return 1ll * a * t.b < 1ll * t.a * b;
}
};
std::vector<Atom> sec;
int main() {
scanf( "%d", &n );
rep ( i, 1, n ) scanf( "%d", &x[i] );
x[n + 1] = x[1];
int circ = 0;
rep ( i, 1, n ) {
int k = iabs( x[i] - x[i + 1] ), d = x[i] < x[i + 1] ? -1 : 1;
rep ( j, 1, k - 1 ) sec.push_back( { j, k, d } );
circ += x[i] >= x[i + 1];
}
sec.push_back( { 0, 1, 0 } ), sec.push_back( { 1, 1, 0 } );
std::sort( sec.begin(), sec.end() );
int ans = 0;
for ( size_t i = 1; i < sec.size(); ++i ) {
if ( ( circ += sec[i - 1].c ) != 1 ) continue;
int dn = sub( mul( sec[i].a, mpow( sec[i].b ) ),
mul( sec[i - 1].a, mpow( sec[i - 1].b ) ) );
int le = ( 1ll * sec[i - 1].a * ( x[1] - x[n] ) % sec[i - 1].b
+ sec[i - 1].b ) % sec[i - 1].b;
if ( !le && x[1] < x[n] ) le = sec[i - 1].b;
le = mul( le, mpow( sec[i - 1].b ) );
int ri = ( 1ll * sec[i].a * ( x[1] - x[n] ) % sec[i].b
+ sec[i].b ) % sec[i].b;
if ( !ri && x[1] > x[n] ) ri = sec[i].b;
ri = mul( ri, mpow( sec[i].b ) );
ans = add( ans, mul( add( le, ri ), dn ) );
}
printf( "%d
", mul( ans, INV6 ) );
return 0;
}